Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

Floyd's Algorithm

Floyd's algorithm  uses the dynamic programming method to solve the all-pairs shortest-path problem on a dense graph. The method makes efficient use of an adjacency matrix to solve the problem. Consider an edge-weighted graph tex2html_wrap_inline71355, where C(v,w) represents the weight on edge (v,w). Suppose the vertices are numbered from 1 to tex2html_wrap_inline71781. I.e., let tex2html_wrap_inline72689. Furthermore, let tex2html_wrap_inline72691 be the set comprised of the first k vertices in tex2html_wrap_inline71357. I.e., tex2html_wrap_inline72697, for tex2html_wrap_inline72699.

Let tex2html_wrap_inline72701 be the shortest path from vertex v to w that passes only through vertices in tex2html_wrap_inline72691, if such a path exists. I.e., the path tex2html_wrap_inline72701 has the form

displaymath72669

Let tex2html_wrap_inline72711 be the length of path tex2html_wrap_inline72701:

displaymath72670

Since tex2html_wrap_inline72715, the tex2html_wrap_inline67626 paths are correspond to the edges of G:

displaymath72671

Therefore, the tex2html_wrap_inline72721 path lengths correspond to the weights on the edges of G:

displaymath72672

Floyd's algorithm computes the sequence of matrices tex2html_wrap_inline72725. The distances in tex2html_wrap_inline72727 represent paths with intermediate vertices in tex2html_wrap_inline72729. Since tex2html_wrap_inline72731, we can obtain the distances in tex2html_wrap_inline72733 from those in tex2html_wrap_inline72727 by considering only the paths that pass through vertex tex2html_wrap_inline71519. Figure gif illustrates how this is done.

   figure52132
Figure: Calculating tex2html_wrap_inline72733 in Floyd's Algorithm

For every pair of vertices (v,w), we compare the distance tex2html_wrap_inline72755, (which represents the shortest path from v to w that does not pass through tex2html_wrap_inline71519) with the sum tex2html_wrap_inline72763 (which represents the shortest path from v to w that does pass through tex2html_wrap_inline71519). Thus, tex2html_wrap_inline72733 is computed as follows:

displaymath72673


next up previous contents index

Bruno Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.