VLSI Digital Signal Processing Systems: Design and Implementation

A.3    THE FLOYD-WARSHALL ALGORITHM

The Floyd-Warshall algorithm is an all-points shortest path algorithm. If no negative cycles exist in the graph, the algorithm finds the shortest path between all possible pairs of nodes in the graph. The algorithm constructs n + 1 matrices ^(k), k = 1, 2, … , n + 1, which are each of size n × n, as described in Figure A.4.

If TRUE is returned, then r⁽ⁿ⁺¹⁾(U, V) is S_UV , which is the shortest path from the node U to the node V. If FALSE is returned, then the graph contains a negative cycle.

Example A.3.1  In this example, the Floyd-Warshall algorithm in Figure A.4 is used to solve the all-pairs shortest path problem for the graph in Figure A.3. The values of r ^(k)(U, V) for U, V ∈ {1, 2, 3, 4} and k = 1, 2, 3, 4, 5 are given in Table A.3, where r^(k)(U, V) is the element U, V in the matrix ^(k) . The Floyd-Warshall algorithm returns TRUE because all of the diagonal elements in the matrices ^(k), k = 1, 2, 3, 4, are nonnegative, so r⁽⁵⁾ (U, V) is the shortest path from the node U to the node V.

Fig. A.4    The Floyd-Warshall algorithm.

Example A.3.2   ...