Algorithms in a Nutshell

All Pairs Shortest Path

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