6.8.  Dijkstra's Algorithm for Finding Minimum Paths

If we wish to find the minimum distance from one given node, to an other node of the graph, one of the most efficient techniques to use is a method called

Dijkstra's algorithm.

The essence of Dijkstra's algorithm is that we discover the minimum distance from the source to other nodes in the order of the those minimum distances, that is closest nodes first. As Dijkstra's algorithm proceeds, we have a situation like that

In the graph there are certain nodes that are settled, that is their minimum distance is known. For the unsettled nodes v, it is easy to find the shortest path. Calculate for every settled node the distance to v:

Minimum(settled nodes, v) = d( , v ).

The shortest path to v is the path < >.

Dijkstra's Algorithm

Let G = (V, E) be a graph with
V = { } =
V = { 1, 2, 3, ... n }
and a start node s and none isolated nodes. This algorithm calculates the shortest path from the node s to every node.

S := set of visited nodes

s := start node, s ∈ S

T := V \ S

d(i) the shortest path from node s to node v(i)

weight(i,j) weight (length) from node to

Examples:

• Page 404, Page 405
  

Last modified 22/May/97