The reason why the Dijkstra’s algorithm can’t handle negative weight edge is that the path to previous selected vertex may be longer than to the vertex which is selected in the future. However, if all negative weight edge is adjacent to s, this situation will not occur. Because after the first iteration, we will not find any negative weight edge.
June 30, 2007
1 Comment »
RSS feed for comments on this post. TrackBack URI
We show that in each iteration of Dijkstra’s algorithm, d[u]= δ(s,u) when u is added to S (the rest follows from the upper-bound property). Let N-(s) be the set of vertices leaving s, which have negative weights. We divide the proof to vertices in N-(s) and all the rest.
Since there are no negative loops, the shortest path between s and all u∈N-(s), is through the edge connecting them to s, hence δ(s,u)=w(s,u), and it follows that after the first time the loop in lines 7,8 is executed d[u]= w(s,u)= δ(s,u) for all u∈N-(s) and by the upper bound property d[u]=δ(s,u) when u is added to S. Moreover it follows that S= N-(s) after |N-(s)| steps of the while loop in lines 4-8.
For the rest of the vertices we argue that the proof of Theorem 24-6 holds since every shortest path from s includes at most one negative edge (and if does it has to be the first one). To see why this is true assume otherwise, which mean that the path contains a loop, contradicting the property that shortest paths do not contain loops.
Comment by jj — May 23, 2009 @ 2:59 am