 INVESTIGATION: Algorithms to finding shortest path

Lesson

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$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 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 that we didn't 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: 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$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$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 Dolby and Belconnen as well: Both through Cambray, $17$17 minutes to Dolby and $18$18 minutes to Belconnen.

Here’s a summary of the algorithm:

Dijkstra's Algorithm
1. Write the order$1$1” and distance$0$0” at the start vertex. This vertex is now the working vertex.
2. Add the distance of the working vertex to the weight of each edge coming out it, writing it as a temporary label at the other end.
• Only write the temporary label if it is smaller than the temporary labels already there.
3. Find the smallest temporary label written at a vertex that hasn’t been a working vertex yet. This vertex is the new working vertex.
4. Add one to the previous order and write it at the new working vertex. Transfer the smallest temporary label to be its distance.
5. If this would be the last working vertex, transfer the final distances to the vertices and highlight the shortest path or paths. Otherwise, repeat this procedure from step $2$2.

Practice using Dijkstra's algorithm in the questions below:

Practice questions

Question 1

In the following graph, we want to find the paths of lowest weight between the vertex $A$A and each of the other vertices. To do this, we will use Dijkstra's algorithm.

1. Perform the first step of the algorithm at the first working vertex, $A$A, by filling in the labels of all its adjacent vertices.

 $1$1 $0$0 $\editable{}$ $\editable{}$
 $\editable{}$ $\editable{}$

 $\editable{}$ $\editable{}$

2. Perform the second step of the algorithm by choosing the next working vertex.

Vertex $A$A

A

Vertex $B$B

B

Vertex $C$C

C

Vertex $D$D

D

Vertex $A$A

A

Vertex $B$B

B

Vertex $C$C

C

Vertex $D$D

D
3. Perform the first step of the algorithm again at the new working vertex by updating the labels of all its adjacent vertices, where appropriate.

To update a label add a comma after the current label number, then write the new label number to form a list.

 $1$1 $0$0 $\editable{}$ $9$9
 $2$2 $3$3

 $\editable{}$ $8$8

4. Perform the second step of the algorithm again by choosing the next working vertex.

Vertex $A$A

A

Vertex $B$B

B

Vertex $C$C

C

Vertex $D$D

D

Vertex $A$A

A

Vertex $B$B

B

Vertex $C$C

C

Vertex $D$D

D
5. Perform the first step of the algorithm again at the new working vertex by updating the labels of all its adjacent vertices, where appropriate.

To update a label add a comma after the current label number, then write the new label number to form a list.

 $1$1 $0$0 $4$4 $9,8$9,8
 $2$2 $3$3

 $3$3 $8,5$8,5

6. For each vertex, enter the least weight between itself and vertex $A$A.

 $0$0 $\editable{}$ $\editable{}$ $\editable{}$

Question 2

Brad has used Dijkstra's algorithm to help him find the paths of lowest weight between one of the vertices and each of the other vertices in the graph shown below.

By using the algorithm, Brad has written down a list of labels next to each vertex.

1. Use the given label lists to number the vertices in order, according to the algorithm.

 $\editable{}$ $0$0 $\editable{}$ $8,6$8,6
 $\editable{}$ $4$4

 $\editable{}$ $10,9$10,9

2. For each vertex, enter the least weight between itself and the starting vertex

 $\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$

Question 3

In the following graph, we want to find the paths of lowest weight between the vertex $A$A and each of the other vertices. To do this, we will use Dijkstra's algorithm.

1. Using the algorithm, fill in the order (upper box) and label list (lower box) for each vertex.

 $\editable{}$ $\editable{}$

 $\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$
 $\editable{}$ $\editable{}$

 $\editable{}$ $\editable{}$

 $\editable{}$ $\editable{}$

2. For each vertex, enter the least weight between itself and vertex $A$A.

 $\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$

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

Brad has used Dijkstra's algorithm to help him find the paths of lowest weight between one of the vertices and each of the other vertices in the graph shown below.

By using the algorithm, Brad has written down a list of labels next to each vertex.

1. Use the given label lists to number the vertices in order, according to the algorithm.

 $\editable{}$ $0$0 $\editable{}$ $8,6$8,6
 $\editable{}$ $4$4

 $\editable{}$ $10,9$10,9

2. For each vertex, enter the least weight between itself and the starting vertex

 $\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$