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_inline70252, where C(v,w) represents the weight on edge (v,w). Suppose the vertices are numbered from 1 to tex2html_wrap_inline70678. That is, let tex2html_wrap_inline71596. Furthermore, let tex2html_wrap_inline71598 be the set comprised of the first k vertices in tex2html_wrap_inline70254. That is, tex2html_wrap_inline71604, for tex2html_wrap_inline71606.

Let tex2html_wrap_inline71608 be the shortest path from vertex v to w that passes only through vertices in tex2html_wrap_inline71598, if such a path exists. That is, the path tex2html_wrap_inline71608 has the form

displaymath71576

Let tex2html_wrap_inline71618 be the length of path tex2html_wrap_inline71608:

displaymath71577

Since tex2html_wrap_inline71622, the tex2html_wrap_inline66793 paths are correspond to the edges of G:

displaymath71578

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

displaymath71579

Floyd's algorithm computes the sequence of matrices tex2html_wrap_inline71632. The distances in tex2html_wrap_inline71634 represent paths with intermediate vertices in tex2html_wrap_inline71636. Since tex2html_wrap_inline71638, we can obtain the distances in tex2html_wrap_inline71640 from those in tex2html_wrap_inline71634 by considering only the paths that pass through vertex tex2html_wrap_inline70416. Figure gif illustrates how this is done.

   figure51665
Figure: Calculating tex2html_wrap_inline71640 in Floyd's algorithm.

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

displaymath71580


next up previous contents index

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