   Next: October 23 Up: October 18 Previous: October 18

Floyd-Warshall all-pairs shortest path

Here's an algorithm that can tolerate negative edges (but not negative cycles, even with only 2 vertices) and returns a table of the shortest distance between all pairs of vertices.

The idea is to first find all the minimal distances for pairs without using any intermediate vertices (this is easy to calculate, since it will be if no edge exists between the pair, the edge weight otherwise). We then relax the restriction, step-by-step: first allow paths that use node 0 as an intermediate, and see whether the minimum distances can be adjusted downwards, then paths that are allowed to use nodes 0 and 1, and so on until all paths are considered. We denote the minimum distance from to that considers intermediate nodes from the set as (special case, doesn't allow any intermediate nodes).

Now we have a way of building up results. If we already know , for , and every pair , then the shortest path from to either passes through or it doesn't. In the first case, the portion of this minimal path from to is itself minimal and doesn't use (convince your self of this), as is the portion from to , so = + . In the second case, equals .

Since we can easily calculate for all pairs , we can build up to (where ) as follows (the third parameter is suppressed, but corresponds to the outer loop parameter in the bottom triply-nested loop):

FLOYD-WARSHALL( V, E )
for  i := 0  to  n-1  do
for  j := 0  to  n-1  do
if  i == j  then
D[i,j] := 0;
else if  (i,j) is in E  then
D[i,j] := w(i,j); /* <-- weight function w */
else
D[i,j] := oo;
end if
end for
end for
for  k := 0  to  n-1  do
for  i := 0  to  n-1  do
for  j := 0  to  n-1  do
if  D[i,k] + D[k,j] < D[i,j]  then
D[i,j] = D[i,k] + D[k,j];
end if
end for
end for
end for
END
Here's something to worry about. How do you know that and correspond to , , and haven't been updated with minimum distances that pass through ?

An easy calculation shows that Floyd-Warshall has complexity, which is consistent with using Dijkstra times (and much simpler). How would you recover a shortest path, given this table of distances?   Next: October 23 Up: October 18 Previous: October 18
Danny Heap 2002-12-16