13.03 Dijkstra's algorithm for shortest paths

There are many applications of networks where the most important question to ask is:

What is the lowest weight path from one vertex to another?

A prominent example in the modern world is GPS routing (to find the shortest travel time between two destinations). In our previous lesson we found the shortest path by observation, however, even for a relatively small network it can often be difficult to find the shortest path efficiently this way. To find the shortest path between two vertices in a systematic way that can be implemented by computer systems on large networks we require an algorithm - a procedure to follow. Let's look at one such procedure:

 

Exploration 

This network represents the travel times for an ambulance to get between the seven townships it services:

The ambulance is parked at the hospital in Eastfarthing when it receives a call for help from Arda. This is an emergency, and the ambulance needs to get there as fast as possible - what route should it take?

First of all, we are going to get rid of the information we won’t be using. We will replace each of the towns with their first letter, move the vertices around a bit, remove the mountains, lakes, and forest, and straighten out the edges:

Take a moment to see how the two networks match up - they are two equivalent representations of the same network.

We are now going to use Dijkstra'a algorithm (pronounced Dike-stra), which was devised by the computer scientist Edsger Dijkstra. He published the algorithm in 1959, three years after he conceived of it, to illustrate the power of computing and coding.

Start by drawing a special box at each vertex like this:

These boxes will record useful numbers as we perform the algorithm. The section in the top left is for the order in which the box is selected (starting at 1 and working upwards). The section in the top right is for the minimum distance between this vertex and the start vertex. The section at the bottom is for temporary labels that we will add to as the procedure continues.

First, we select the start vertex, or working vertex, in this case $E$E. Since we picked it first, we put a “$1$1” in the order section, and since there is no distance from $E$E to itself, we put a “$0$0” in the distance section.

Next, we follow each edge coming out of this working vertex, and write the weight of the edge in the temporary section of the vertex at the other end:

We are now finished with this vertex and will move on to the next one. We find the smallest temporary label on the unused vertices (which is $G$G), mark its order as “$2$2” (since it’s second) and transfer the temporary label (which is $6$6) to be its new minimum distance.

 

This is now the working vertex. We repeat the same procedure to record temporary labels, but this time

• We add the distance of the working vertex (which is $6$6) to the weight of each edge, and
• We only write the number as a new temporary label if it’s less than the temporary labels we've already written (which only happens at $B$B):

Note: We didn't need to write $18$18 at $F$F or $22$22 at $C$C, since there was a smaller temporary label already written at the bottom.

Now we loop back through the algorithm and choose a new working vertex (the one with the smallest temporary label, which is $F$F) and update its order and distance sections:

The algorithm is repeated steps of writing temporary labels of the minimum distance found so far from the start vertex to each vertex we can reach and then locking in the vertex with the smallest temporary label. Repeat until all vertices are labelled or you can stop when the target vertex becomes the working vertex. When we lock in a vertex and it becomes our working vertex you have found the minimum distance from the start vertex to that vertex.

Let's continue, we do the same as we did before, adding the distance to the weight of each edge and adjusting the temporary labels:

Note: This time we do write $20$20 as a new temporary label, since it is less than the existing temporary label.

Once again we pick a new working vertex, updating its order and distance:

And update the temporary labels for edges coming out of the working vertex:

Then pick a new working vertex, updating its order and distance:

And update the temporary label at vertex $A$A:

One more time! We pick the new working vertex:

And write the last temporary label:

The last vertex that hasn’t been picked (which is $A$A) is not going to be a working vertex, but we update its order and distance fields in the same way:

The procedure is now complete! We now don’t need any numbers except the final distances. We transfer those onto the vertices themselves:

The shortest paths have been highlighted as well - starting at $E$E, we pick the edges that make the shortest paths to each vertex, making sure the weights match up with our answers.

Now we know how the ambulance should travel from Eastfarthing to Arda, and how long it will take: Through Cambray then Belconnen on the way to Arda, and it will take $22$22 minutes.

In fact, we know the fastest route and travel times from the station to each town, for example the shortest travel time to Dolby and Belconnen are both through Cambray, $17$17 minutes to Dolby and $18$18 minutes to Belconnen.

 

This procedure, once completed, tells us the weight of the lowest weight path from the start vertex to each of the vertices in the network.

It is guaranteed to give us the right answer by looping through a sequence of structured steps. This means it is very suitable to be done by a computer program - the complexity of the network then becomes irrelevant, since a computer can do this kind of algorithm extremely quickly. Every time you ask for directions from an online service, this algorithm or one similar will be performed in the background.

Here’s a summary of the algorithm: