All Pairs Shortest Path
Instead of finding the shortest path from a single source, we often want to find a shortest path between any two vertices (vi,vj). The fastest solution to this problem uses a powerful problem-solving technique called dynamic programming.
There are two interesting features of dynamic programming:
It solves small, constrained versions of the problem. When the constraints are tight, the function is simple to compute, and then the constraints are systematically relaxed until finally they yield the value of the desired answer.
Although one seeks an optimum answer to a problem, it is easier to compute the value of an optimum answer rather than the answer itself. In our case, we compute, for each pair of vertices (vi,vj), the length of a shortest path from vi to vj and perform additional computation to recover the actual path.
The goal is to compute an n-by-n matrix
dist such that for all pairs of vertices (vi,vj),
dist[i][j] contains the length of a shortest path from vi to vj. The pseudocode for Floyd-Warshall is shown in Figure 6-18, together with its execution on a small example.
Figure 6-18. Floyd-Warshall fact sheet
A directed, weighted graph G=(V, E). Each edge e=(u, v) has an associated positive weight in the graph. The quantity n represents the number of vertices in G.
Floyd-Warshall produces the matrix
dist of values representing the shortest ...