7

I've been studying all-pair shortest path algorithms recently such as Floyd-Warshall and Johnson's algorithm, and I've noticed that these algorithms produce correct solutions even when a graph contains negative weight edges (but not negative weight cycles). For comparison, Dijkstra's algorithm (which is single-source shortest path) does not work for negative weight edges. What makes the all-pair shortest path algorithms work with negative weights?

  • It might be instructive to learn why Dijkstra's algorithm _doesn't_ work with negative weights: http://stackoverflow.com/questions/13159337/why-dijkstras-algo-not-work-for-negative-weight-edges – Thomas Apr 06 '14 at 08:03

2 Answers2

7

Floyd Warshall's all pairs shortest paths algorithm works for graphs with negative edge weights because the correctness of the algorithm does not depend on edge's weight being non-negative, while the correctness of Dijkstra's algorithm is based on this fact.

Correctness of Dijkstra's algorithm:

We have 2 sets of vertices at any step of the algorithm. Set A consists of the vertices to which we have computed the shortest paths. Set B consists of the remaining vertices.

Inductive Hypothesis: At each step we will assume that all previous iterations are correct.

Inductive Step: When we add a vertex V to the set A and set the distance to be dist[V], we must prove that this distance is optimal. If this is not optimal then there must be some other path to the vertex V that is of shorter length.

Suppose this some other path goes through some vertex X in the set B.

Now, since dist[V] <= dist[X] , therefore any other path to V will be atleast dist[V] length, unless the graph has negative edge lengths.

Correctness of Floyd Warshall's algorithm: Any path from vertex S to vertex T, will go through any other vertex U of the graph. Thus the shortest path from S to T can be computed as the

min( shortest_path(S to U) + shortest_path(U to T)) for all vertices U in the graph.

As you can see there is no dependence on the graph's edges to be non-negative as long as the sub calls compute the paths correctly. And the sub calls compute the paths correctly as long as the base cases have been properly initialized.

Nikunj Banka
  • 11,117
  • 16
  • 74
  • 112
  • You can't just say "Now, since dist[V] <= dist[X]", at least not without qualifying X a bit more. I think what you need here is to say "Suppose this some other path goes through some vertex X *in B.*" in the previous sentence, and explain why it's not necessary to consider the case where X is in A. – j_random_hacker Apr 06 '14 at 12:32
  • If the path has to go through some vertex of set A then it will directly start from that vertex. I thought this too basic not to add. However I have added that "X is in set B". Thanks for pointing out. – Nikunj Banka Apr 06 '14 at 12:55
0

Dijkstra's Algorithm doesn't work for negative weight edge because it is based on the greedy strategy(an assumption) that once a vertex v was added to the set S, d[v] contains the minimum distance possible.

But if the last vertex in Q was added to S and it has some outgoing negative weight edges. The effects on the distance that caused by negative edges won't count.

However, all pairs shortest paths algorithm will capture those updates.

Robert.Li
  • 169
  • 1
  • 7