Dijkstra’s algorithm generates the shortest path tree from a given node to any (or every) other node in the network.
Although the problem that we will use as an example is fairly trivial and can be solved by inspection, the technique that we will use can be applied to much larger problems.
Dijkstra’s algorithm requires that each node in the network be assigned values (labels). There is a working label and a permanent label, as well as an ordering label. Whilst going through the steps of the algorithm you will assign a working label to each vertex. The smallest working label at each iteration will become permanent.
The steps of Dijkstra’s algorithm are:
- Give the start point the permanent label of 0, and the ordering label 1.
- Any vertex directly connected to the last vertex given a permanent label is assigned a working label equal to the weight of the connecting edge added to the permanent label you are coming from. If it already has a working label replace it only if the new working label is lower.
- Select the minimum current working value in the network and make it the permanent label for that node.
- If the destination node has a permanent label go to step 5, otherwise go to step 2.
- Connect the destination to the start, working backwards. Select any edge for which the difference between the permanent labels at each end is equal to the weight of the edge.
It is a good idea to use a system for keeping track of the current working labels and the ordering and permanent labels of each of the nodes in the network. The system that I recommend is that found in Parramore et al (2004). A small grid is drawn near each of the nodes, working labels are written in the lower box, ordering labels in the upper left box, and permanent labels in the upper right box, as shown in figure 1.
Figure 1: Labelling system for Dijkstra's Algorithm.
In this example we will consider the network in figure 2. We would like to find the shortest path from node A to node H.
Figure 2: Example of a network with labels assigned.
In this example the working, permanent, and ordering labels have already been assigned to each node following the steps above. As you can see, the destination node (node H) has a permanent label. This means that a shortest route from A to H has been found, even though there is no permanent label for node E.
The shortest route is found by tracing back from the destination node (node H) to the start (node A), selecting each edge for which the difference between permanent values at its terminating nodes is equal to the weight of the edge. The shortest routes for this network are shown in figure 3 below. The edges shown in green (AB and BC) are an alternative to the edge AC shown in red. In this case there are two equivalent shortest routes from A to H.
Figure 3: The shortest routes from A to H in this network.