With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

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

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required