Implementation

Data Structures and Algorithms with Object-Oriented Design Patterns in C#

Implementation

An implementation of Dijkstra's algorithm is shown in Program . The DijkstrasAlgorithm method takes two arguments. The first is a directed graph. It is assumed that the directed graph is an edge-weighted graph in which the weights are ints. The second argument is the number of the start vertex, .

The DijkstrasAlgorithm method returns its result in the form of a shortest-path graph. Therefore, the return value is a Digraph instance.

program51613
Program: Dijkstra's algorithm.

The main data structures used are called table and queue (lines 6 and 12). The former is an array of Entry elements. The latter is a priority queue. In this case, a BinaryHeap of length is used. (See Section ).

The algorithm begins by setting the tentative distance for the start vertex to zero and inserting the start vertex into the priority queue with priority zero (lines 10-12).

The main loop of the method comprises lines 13-33. In each iteration of this loop the vertex with the smallest distance is dequeued (line 15). The vertex is processed only if its table entry indicates that the shortest path is not already known (line 17).

When a vertex v0 is processed, its shortest path is deemed to be known (line 19). Then each vertex v1 adjacent to vertex is considered (lines 20-31). The distance to v1 along the path that passes through v0 is computed (lines 23-24). If this distance is less than the tentative distance associated with v1, entries in the table for v1 are updated, and the v1 is given a new priority and inserted into the priority queue (lines 25-30).

The main loop terminates when all the shortest paths have been found. The shortest-path graph is then constructed using the information in the table (lines 34-39).