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

Implementation

An implementation of Floyd's algorithm is shown in Program gif. The FloydsAlgorithm method takes as its argument a directed graph. The directed graph is assumed to be an edge-weighted graph in which the weights are ints.

   program51806
Program: Floyd's algorithm.

The FloydsAlgorithm method returns its result in the form of an edge-weighted directed graph. Therefore, the return value is a Digraph.

The principal data structure use by the algorithm is a tex2html_wrap_inline70792 matrix of integers called distance. All the elements of the matrix are initially set to tex2html_wrap_inline68188 (lines 6-9). Next, an edge enumerator is used to visit all the edges in the input graph in order to transfer the weights from the graph to the distance matrix (lines 11-14).

The main work of the algorithm is done in three, nested loops (lines 16-25). The outer loop computes the sequence of distance matrices tex2html_wrap_inline71684. The inner two loops consider all possible pairs of vertices. Notice that as tex2html_wrap_inline71640 is computed, its entries overwrite those of tex2html_wrap_inline71634.

Finally, the values in the distance matrix are transfered to the result graph (lines 27-33). The result graph contains the same set of vertices as the input graph. For each finite entry in the distance matrix, a weighted edge is added to the result graph.


next up previous contents index

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