|
Data Structures and Algorithms
with Object-Oriented Design Patterns in C# |
The implementation of Dijkstra's algorithm described below
uses the Entry struct declared in Program 
.
Each Entry value has three fields,
known, distance, and predecessor,
which correspond to the variables
, 
, and 
, respectively.
Program: GraphAlgorithms Entry struct.
In each pass of its operation, Dijkstra's algorithm selects from the set of vertices for which the shortest-path is not yet known the one with the smallest tentative distance. Therefore, we use a priority queue to represent this set of vertices.
The priority assigned to a vertex is its tentative distance.
The class Association class introduced in Program
is used to associate a priority with a given vertex instance.
Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.