|
Data Structures and Algorithms
with Object-Oriented Design Patterns in C# |
An implementation of Floyd's algorithm is shown in Program 
.
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.
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 
matrix of integers called distance.
All the elements of the matrix are initially set to 
(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
.
The inner two loops consider all possible pairs of vertices.
Notice that as 
is computed, its entries overwrite those of 
.
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.
Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.
