Why do all-pair shortest path algorithms work with negative weights?

Question

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?

Answer 1

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.

Answer 2

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.