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

### Dijkstra's Algorithm

Dijkstra's algorithm  is a greedy algorithm for solving the single-source, shortest-path problem on an edge-weighted graph in which all the weights are non-negative. It finds the shortest paths from some initial vertex, say , to all the other vertices one-by-one. The essential feature of Dijkstra's algorithm is the order in which the paths are determined: The paths are discovered in the order of their weighted lengths, starting with the shortest, proceeding to the longest.

For each vertex v, Dijkstra's algorithm keeps track of three pieces of information, , , and :

The Boolean-valued flag indicates that the shortest path to vertex v is known. Initially, for all .
The quantity is the length of the shortest known path from to v. When the algorithm begins, no shortest paths are known. The distance is a tentative distance. During the course of the algorithm candidate paths are examined and the tentative distances are modified.

Initially, for all such that , while .

The predecessor of vertex v on the shortest path from to v. I.e., the shortest path from to v has the form .

Initially, is unknown for all .

Dijkstra's algorithm proceeds in phases. The following steps are performed in each pass:

1. From the set of vertices for with , select the vertex v having the smallest tentative distance .
2. Set .
3. For each vertex w adjacent to v for which , test whether the tentative distance is greater than . If it is, set and set .
In each pass exactly one vertex has its set to true. The algorithm terminates after passes are completed at which time all the shortest paths are known.

Table  illustrates the operation of Dijkstra's algorithm as it finds the shortest paths starting from vertex b in graph shown in Figure .

 passes vertex initially 1 2 3 4 5 6 a 3 b 3 b 3 b 3 b 3 b 3 b b 0 -- 0 -- 0 -- 0 -- 0 -- 0 -- 0 -- c 5 b 4 a 4 a 4 a 4 a 4 a d 6 c 6 c 6 c 6 c e 8 c 8 c 8 c 8 c f 11 d 9 e 9 e

Initially all the tentative distances are , except for vertex b which has tentative distance zero. Therefore, vertex b is selected in the first pass. The mark beside an entry in Table  indicates that the shortest path is known ( ).

Next we follow the edges emanating from vertex b, and , and update the distances accordingly. The new tentative distances for a becomes 3 and the new tentative distance for c is 5. In both cases, the next-to-last vertex on the shortest path is vertex b.

In the second pass, vertex a is selected and its entry is marked with indicating the shortest path is known. There is one edge emanating from a, . The distance to c via a is 4. Since this is less than the tentative distance to c, vertex c is given the new tentative distance 4 and its predecessor on the shortest-path is set to a. The algorithm continues in this fashion for a total of passes until all the shortest paths have been found.

The shortest-path information contained in the right-most column of Table  can be represented in the form of a vertex-weighted graph as shown in Figure .

Figure: The Shortest-Path Graph for

This graph contains the same set of vertices as the problem graph . Each vertex v is labeled with the length of the shortest path from b to v. Each vertex (except b) has a single emanating edge that connects the vertex to the next-to-last vertex on the shortest-path. By following the edges in this graph from any vertex v to vertex b, we can construct the shortest path from b to v in reverse.