Logo Data Structures and Algorithms with Object-Oriented Design Patterns in Java
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_inline70093, where C(v,w) represents the weight on edge (v,w). Suppose the vertices are numbered from 1 to tex2html_wrap_inline70519. That is, let tex2html_wrap_inline71437. Furthermore, let tex2html_wrap_inline71439 be the set comprised of the first k vertices in tex2html_wrap_inline70095. That is, tex2html_wrap_inline71445, for tex2html_wrap_inline71447.

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

displaymath71417

Let tex2html_wrap_inline71459 be the length of path tex2html_wrap_inline71449:

displaymath71418

Since tex2html_wrap_inline71463, the tex2html_wrap_inline66606 paths are correspond to the edges of G:

displaymath71419

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

displaymath71420

Floyd's algorithm computes the sequence of matrices tex2html_wrap_inline71473. The distances in tex2html_wrap_inline71475 represent paths with intermediate vertices in tex2html_wrap_inline71477. Since tex2html_wrap_inline71479, we can obtain the distances in tex2html_wrap_inline71481 from those in tex2html_wrap_inline71475 by considering only the paths that pass through vertex tex2html_wrap_inline70257. Figure gif illustrates how this is done.

   figure51527
Figure: Calculating tex2html_wrap_inline71481 in Floyd's algorithm.

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

displaymath71421


next up previous contents index

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