Instead of finding the shortest path from a single source, we often want to find a shortest path^{[26]} between any two vertices (*v*_{i},*v*_{j}). 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 (*v*_{i},*v*_{j}), the length of a shortest path from*v*_{i}to*v*_{j}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 (*v*_{i},*v*_{j}), `dist[i][j]`

contains the length of a shortest path from *v*_{i} to *v*_{j}. 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

**Input**

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*.

**Output**

Floyd-Warshall produces the matrix `dist[][]`

of values representing the shortest ...

Start Free Trial

No credit card required