INVESTIGATION: Algorithms to finding shortest path

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). Dijkstra's algorithm, was conceived by computer scientist Edsger W. Dijkstra in 1956 and is another procedure to find the shortest path between two vertices in a network.

It is guaranteed to give us the right answer by looping through a sequence of simple 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 is exactly how it will figure it out for you.

Consider the ambulance problem from lesson 4.04:

The ambulance is now parked at 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?

The corresponding network is shown below:

 

Dijkstra's algorithm starts 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 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. Since we picked it first, we put a “1” in the order section, and since there is no distance from E to itself, we put a “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), mark its order as “2” (since it’s second) and transfer the temporary label (which is 6) to be its new 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) 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):

Note that we didn't write 18 at F or 22 at 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) and update its order and distance sections:

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

This time we do write 20, 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:

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) 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, 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 minutes.

In fact, we know the fastest route and travel times from the station to Dolby and Belconnen as well: Both through Cambray, 17 minutes to Dolby and 18 minutes to Belconnen.

Here’s a summary of the algorithm:

Practice using Dijkstra's algorithm in the questions below:

Practice questions

Question 1

Question 2

Question 3

Questions

• Can you design a problem of your own and use Dijkstra's algorithm to solve it? For example: draw a network to represent the possible routes from your home to school and use Dijkstra's algorithm to decide the shortest path.
• Is the shortest path always calculated by distance, or would the time taken to travel the edges be a better indicator of the shortest route?
• Do car navigation systems use Dijkstra's algorithm to determine shortest path? Where else is Dijkstra's algorithm used in the real world?
• What might be a problem using Dijkstra's algorithm in a large graph such as Google maps?
• Compare these animations of Dijkstra's algorithm with the A* algorithm. Which might be more efficient for a large graph? 
• Does Dijkstra's algorithm also work for directed networks? Investigate using this question:

Question 4