This Woman is really cute - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>CS - 计算机科学

This Woman is really cute

This Woman is really cute# CS - 计算机科学

A*l2005-05-30 07:05

1 楼

比武招“亲” 聪明的gg在哪里？...
下面这条题目我做了一个星期都没搞定。
" 给定图G(V,E)和每条边的权重函数(注意：权重可为负)
假定已经完成了最短路径的计算，你意识到你计算时每条边的
权重都少算了k(k>0). 请提供一个O(E)的算法能求出正确的最
短路径解。你的算法应该和k无关。"
哪个gg能一周内做出来就是比我聪明的gg。
我就bg他大餐并亲他一下。而且一直崇拜他。no kidding
嗯嗯，我大四，CS系
版猪我是认真的想认识聪明的gg做bf。
那样我的作业就都不用愁了。啦啦啦
也许CS系的gg还能有点希望吧
回我信箱。^Q^
拍砖的拍版面好啦，就不要拍到我信箱啦，版猪不会帮我整理信箱的
http://www.newsmth.com/bbscon.php?bid=398&id=186787&ap=837

w*g2005-05-30 07:05

2 楼

我给学生出过这道题。这妞也太笨了。

【在 A***l 的大作中提到】

: 比武招“亲” 聪明的gg在哪里？...
: 下面这条题目我做了一个星期都没搞定。
: " 给定图G(V,E)和每条边的权重函数(注意：权重可为负)
: 假定已经完成了最短路径的计算，你意识到你计算时每条边的
: 权重都少算了k(k>0). 请提供一个O(E)的算法能求出正确的最
: 短路径解。你的算法应该和k无关。"
: 哪个gg能一周内做出来就是比我聪明的gg。
: 我就bg他大餐并亲他一下。而且一直崇拜他。no kidding
: 嗯嗯，我大四，CS系
: 版猪我是认真的想认识聪明的gg做bf。

X*r2005-05-30 07:05

3 楼

我k
她以为她是who？

【在 A***l 的大作中提到】

X*r2005-05-30 07:05

4 楼

你可以亲她一下了

【在 w*******g 的大作中提到】

: 我给学生出过这道题。这妞也太笨了。

w*g2005-05-30 07:05

5 楼

她以为她是谁？

【在 X*****r 的大作中提到】

: 你可以亲她一下了

v*u2005-05-30 07:05

6 楼

How? //shy

【在 w*******g 的大作中提到】

: 我给学生出过这道题。这妞也太笨了。

w*g2005-05-30 07:05

7 楼

just go through the graph edge by edge and determine whether the current
edge is the shortest path between its end points. the algorithm is of course
related to k though the complexity is not.

【在 v*****u 的大作中提到】

: How? //shy

r*c2005-05-30 07:05

8 楼

still do not understand why it is O(E)
it seems that determine current edge is O(1) from your solution

【在 w*******g 的大作中提到】

: just go through the graph edge by edge and determine whether the current
: edge is the shortest path between its end points. the algorithm is of course
: related to k though the complexity is not.

t*g2005-05-30 07:05

9 楼

每条边的权重少算了k是什么意思？
实际权重函数是w(e)，但计算时用的是w'(e) = w(e) - k?

【在 w*******g 的大作中提到】

: 我给学生出过这道题。这妞也太笨了。

w*g2005-05-30 07:05

10 楼

since the shortest path is already computed, you may assume that you know
the weight and the edge count of the shortest path between any two vertices.

【在 r****c 的大作中提到】

: still do not understand why it is O(E)
: it seems that determine current edge is O(1) from your solution

r*c2005-05-30 07:05

11 楼

Faint
The problem is not clear and well defined
It is said that "the shortest path is already computed" is it mean a certain
pair of
source and destination or all pairs
for the objective: find the new shortest path is mean the all pairs
if all pairs, it could not be O(E)
Btw, even the objective is for a fixed pair of end points,
do not understand your solution
"just go through the graph edge by edge and determine whether the current
edge is the shortest path between its end points. the algorithm

【在 w*******g 的大作中提到】

: since the shortest path is already computed, you may assume that you know
: the weight and the edge count of the shortest path between any two vertices.

w*g2005-05-30 07:05

12 楼

should be single-source shortest path. for all end-points, it takes O(n^2)
to even report the results.
you can do a breadth first search starting from the source and do edge
relaxation as in Bellman-ford's algorithm. In this setting, only shorter
path can replace longer path so that there is no need to backtrack.

【在 r****c 的大作中提到】

: Faint
: The problem is not clear and well defined
: It is said that "the shortest path is already computed" is it mean a certain
: pair of
: source and destination or all pairs
: for the objective: find the new shortest path is mean the all pairs
: if all pairs, it could not be O(E)
: Btw, even the objective is for a fixed pair of end points,
: do not understand your solution
: "just go through the graph edge by edge and determine whether the current

t*s2005-05-30 07:05

13 楼

what if k here is very big...
if k is greater than all the edge weight, and if the graph is connected
pairwise, then all the "known" shortest edge length would be negative
infinity....which simply tells us nothing...
so G here must be acyclic?

【在 A***l 的大作中提到】

w*g2005-05-30 07:05

14 楼

for shortest path problem, if there is negative weight, then it is usually
assumed that the graph is directed and doesn't contain negative cycle.

【在 t*s 的大作中提到】

: what if k here is very big...
: if k is greater than all the edge weight, and if the graph is connected
: pairwise, then all the "known" shortest edge length would be negative
: infinity....which simply tells us nothing...
: so G here must be acyclic?

w*g2005-05-30 07:05

15 楼

if that is the case, smart girl. hehe.
did you get your kiss?

【在 A***l 的大作中提到】

t*s2005-05-30 07:05

16 楼

and where did you get your kiss...

【在 w*******g 的大作中提到】

: if that is the case, smart girl. hehe.
: did you get your kiss?

w*g2005-05-30 07:05

17 楼

I got my kiss from various girlfriends of mine.

【在 t*s 的大作中提到】

: and where did you get your kiss...

c*m2005-05-30 07:05

18 楼

Could you please explain how to exam each edge? Thanks.
Given the shortest path between any pair, how to compute
the shortest path after adding k?
Besides, maybe what is given is only the shortest path to
one specific source node.

【在 w*******g 的大作中提到】

: since the shortest path is already computed, you may assume that you know
: the weight and the edge count of the shortest path between any two vertices.

w*g2005-05-30 07:05

19 楼

yeah. it is single-source shortest path. just use breadth first search
and update the distance of every node from the source by examing each edge.

【在 c******m 的大作中提到】

: Could you please explain how to exam each edge? Thanks.
: Given the shortest path between any pair, how to compute
: the shortest path after adding k?
: Besides, maybe what is given is only the shortest path to
: one specific source node.

v*u2005-05-30 07:05

20 楼

The provided condition is not very clear.
According the answer of wildThing, we know shortest path and weight
between every two vertices

【在 c******m 的大作中提到】

w*g2005-05-30 07:05

21 楼

actually, that was not needed. Since this is a single-source shortest path
problem, you only assume the existing of the shortest path between the source
and other nodes.

【在 v*****u 的大作中提到】

: The provided condition is not very clear.
: According the answer of wildThing, we know shortest path and weight
: between every two vertices

v*u2005-05-30 07:05

22 楼

I am more confused.
Can you explain more specifically how to do the breath-first search?
How to update the weight every step?
The girl is smart. Hard to get dinner and kiss.

【在 w*******g 的大作中提到】

: actually, that was not needed. Since this is a single-source shortest path
: problem, you only assume the existing of the shortest path between the source
: and other nodes.

w*g2005-05-30 07:05

23 楼

hmmm, it is not exactly BFS.
This is not the same problem as the one that I dealt with before :(
I think the solution should be that
assume each node u is given the total weight (d(u)) and
the # of edges (let's call it k(u)) of the shortest path from the source v.
Based on the new weights of all edges,
update the shortest path of all nodes have edges from u where k(u)=1
and then update the shortest path of all nodes with edges from u where k(u) = 2,
and then update the shortest path of all nodes

【在 v*****u 的大作中提到】

: I am more confused.
: Can you explain more specifically how to do the breath-first search?
: How to update the weight every step?
: The girl is smart. Hard to get dinner and kiss.

t*s2005-05-30 07:05

24 楼

you don't know k(u)
even if you know k(u)
you need to go from k(u)=1 to what? to |V|
what if the graph is sparse? |V| might be bigger...

【在 w*******g 的大作中提到】

: hmmm, it is not exactly BFS.
: This is not the same problem as the one that I dealt with before :(
: I think the solution should be that
: assume each node u is given the total weight (d(u)) and
: the # of edges (let's call it k(u)) of the shortest path from the source v.
: Based on the new weights of all edges,
: update the shortest path of all nodes have edges from u where k(u)=1
: and then update the shortest path of all nodes with edges from u where k(u) = 2,
: and then update the shortest path of all nodes

w*g2005-05-30 07:05

25 楼

you know k(u) because that is a derived info from shortest path.
k(u) can be |V| but it doesn't matter because you visit each edge at most once.

【在 t*s 的大作中提到】

: you don't know k(u)
: even if you know k(u)
: you need to go from k(u)=1 to what? to |V|
: what if the graph is sparse? |V| might be bigger...

r*c2005-05-30 07:05

26 楼

Yeah you are right
actually, we can find the shortest path tree not only a pair of shortest path
the key observation is that every edge is considered at most once,
can you imagine how to find the all shortest path in O(E)?

once.
v.
k(u) = 2,
k(u) = 3,
previously
complexity

【在 w*******g 的大作中提到】

: you know k(u) because that is a derived info from shortest path.
: k(u) can be |V| but it doesn't matter because you visit each edge at most once.

m*r2005-05-30 07:05

27 楼

Can we solve this problem using Dijkstra's algorithm directly from start given
G(V,E,W)?

path
source

【在 r****c 的大作中提到】

: Yeah you are right
: actually, we can find the shortest path tree not only a pair of shortest path
: the key observation is that every edge is considered at most once,
: can you imagine how to find the all shortest path in O(E)?
:
: once.
: v.
: k(u) = 2,
: k(u) = 3,
: previously

P*f2005-05-30 07:05

28 楼

Dijstra's algorithm is not applicable when negative edge exists

【在 m*****r 的大作中提到】

: Can we solve this problem using Dijkstra's algorithm directly from start given
: G(V,E,W)?
:
: path
: source

w*g2005-05-30 07:05

29 楼

dijkstra's algorithm only works for non-negative weight graph.

【在 m*****r 的大作中提到】

: Can we solve this problem using Dijkstra's algorithm directly from start given
: G(V,E,W)?
:
: path
: source

c*m2005-05-30 07:05

30 楼

How to update the shortest path with k(u)>1 within constant time?
Things might be complex..., not necessary to follow the path we already have

【在 w*******g 的大作中提到】

c*m2005-05-30 07:05

31 楼

There is some algorithm can transform graph with negative edge to non-negative
graph, within O(E) time, while keep the shortest path, given the shortest path
solution
You can refer to section 5.5 in
http://www.cs.wisc.edu/wpis/abstracts/jalg96.abs.html
But the Dijkstra still needs O(E+VlogV)

【在 w*******g 的大作中提到】

: dijkstra's algorithm only works for non-negative weight graph.

w*g2005-05-30 07:05

32 楼

It is possible to solve graph with negative weight using algorithm that applies
to positive weight graph but the transformation is not better than O(|E||V|).

【在 c******m 的大作中提到】

: There is some algorithm can transform graph with negative edge to non-negative
: graph, within O(E) time, while keep the shortest path, given the shortest path
: solution
: You can refer to section 5.5 in
: http://www.cs.wisc.edu/wpis/abstracts/jalg96.abs.html
: But the Dijkstra still needs O(E+VlogV)

w*g2005-05-30 07:05

33 楼

You don't follow the same shortest path as before.
You only update the nodes that are neighbors of u where k(u) = i for each i.
The key here is that for a unknown graph, you don't know how long is the shortest
path from source to the destination. That is why Bellman-Ford's algorithm needs
|V| iterations.
For this problem, that distance of the shortest path between v and u
is bounded by the distance of the previous shortest path and
you can find out the new shortest path by a BSF-like traversal

【在 c******m 的大作中提到】

: How to update the shortest path with k(u)>1 within constant time?
: Things might be complex..., not necessary to follow the path we already have

c*m2005-05-30 07:05

34 楼

Can u provide more details on how to update node u when k(u) = i, when i > 1
Say, if i = 3, how to update the nodes with k(u) = 3 ? We can not garentee
the optimal if we only check the incoming edges which ends at this node, and
come from nodes with k(u) < 3, the new shortest path might come from nodes
with k(u) > 3, which we havn't updated. How to deal with it?

【在 w*******g 的大作中提到】

:
: You don't follow the same shortest path as before.
: You only update the nodes that are neighbors of u where k(u) = i for each i.
: The key here is that for a unknown graph, you don't know how long is the shortest
: path from source to the destination. That is why Bellman-Ford's algorithm needs
: |V| iterations.
: For this problem, that distance of the shortest path between v and u
: is bounded by the distance of the previous shortest path and
: you can find out the new shortest path by a BSF-like traversal

w*g2005-05-30 07:05

35 楼

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
yeah, let's call this node u' where k(u') = i > 3 and
if (u', u) is an edge, then at ith iteration, we update the shortest path
to u based on the new path to u'.
The point is that the shortest path to a node u is finalized when we reach
ith iteration where i = k(u).
At this point, we can use this result to update the neighbors of u.

【在 c******m 的大作中提到】

: Can u provide more details on how to update node u when k(u) = i, when i > 1
: Say, if i = 3, how to update the nodes with k(u) = 3 ? We can not garentee
: the optimal if we only check the incoming edges which ends at this node, and
: come from nodes with k(u) < 3, the new shortest path might come from nodes
: with k(u) > 3, which we havn't updated. How to deal with it?

c*m2005-05-30 07:05

36 楼

So basicly, you are doing a BFS, and once the depth in BFS exceed k(u),
you finalized the value on u,
Each edge is computed once for BFS and once for finalization, so the overall
complexity is O(E), am I right?

【在 w*******g 的大作中提到】

:
: ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
: yeah, let's call this node u' where k(u') = i > 3 and
: if (u', u) is an edge, then at ith iteration, we update the shortest path
: to u based on the new path to u'.
: The point is that the shortest path to a node u is finalized when we reach
: ith iteration where i = k(u).
: At this point, we can use this result to update the neighbors of u.

r*c2005-05-30 07:05

37 楼

The key observation is that if node v_i is x hops away from the
source, then v_i can not be more than x hops from the new graph
when every edge weight plus k

have
i.
shortest
needs
traversal

【在 c******m 的大作中提到】