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

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 tex2html_wrap_inline70863, 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, tex2html_wrap_inline70999, tex2html_wrap_inline71001, and tex2html_wrap_inline71003:

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

Initially, tex2html_wrap_inline71025 for all tex2html_wrap_inline71013 such that tex2html_wrap_inline71029, while tex2html_wrap_inline71031.

tex2html_wrap_inline71003
The predecessor of vertex v on the shortest path from tex2html_wrap_inline70863 to v. That is, the shortest path from tex2html_wrap_inline70863 to v has the form tex2html_wrap_inline71045.

Initially, tex2html_wrap_inline71003 is unknown for all tex2html_wrap_inline71013.

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

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

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

 

 

passes

vertex

initially 1 2 3 4 5 6
a tex2html_wrap_inline67905 3 b tex2html_wrap_inline71087 3 b tex2html_wrap_inline71087 3 b tex2html_wrap_inline71087 3 b tex2html_wrap_inline71087 3 b tex2html_wrap_inline71087 3 b
b 0 -- tex2html_wrap_inline71087 0 -- tex2html_wrap_inline71087 0 -- tex2html_wrap_inline71087 0 -- tex2html_wrap_inline71087 0 -- tex2html_wrap_inline71087 0 -- tex2html_wrap_inline71087 0 --
c tex2html_wrap_inline67905 5 b 4 a tex2html_wrap_inline71087 4 a tex2html_wrap_inline71087 4 a tex2html_wrap_inline71087 4 a tex2html_wrap_inline71087 4 a
d tex2html_wrap_inline67905 tex2html_wrap_inline67905 tex2html_wrap_inline67905 6 c tex2html_wrap_inline71087 6 c tex2html_wrap_inline71087 6 c tex2html_wrap_inline71087 6 c
e tex2html_wrap_inline67905 tex2html_wrap_inline67905 tex2html_wrap_inline67905 8 c 8 c tex2html_wrap_inline71087 8 c tex2html_wrap_inline71087 8 c
f tex2html_wrap_inline67905 tex2html_wrap_inline67905 tex2html_wrap_inline67905 tex2html_wrap_inline67905 11 d 9 e tex2html_wrap_inline710879e
Table: Operation of Dijkstra's algorithm.

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

Next we follow the edges emanating from vertex b, tex2html_wrap_inline71219 and tex2html_wrap_inline71221, 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 tex2html_wrap_inline71087 indicating the shortest path is known. There is one edge emanating from a, tex2html_wrap_inline71239. 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 tex2html_wrap_inline69999 passes until all the shortest paths have been found.

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

   figure51100
Figure: The shortest-path graph for tex2html_wrap_inline70947.

This graph contains the same set of vertices as the problem graph tex2html_wrap_inline70947. Each vertex v is labeled with the length tex2html_wrap_inline71001 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.


next up previous contents index

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