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
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:
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.
Perform the first step of the algorithm at the first working vertex, $A$A, by filling in the labels of all its adjacent vertices.
|
|||||||||
|
|
||||||||
|
Perform the second step of the algorithm by choosing the next working vertex.
Vertex $A$A
Vertex $B$B
Vertex $C$C
Vertex $D$D
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.
|
|||||||||
|
|
||||||||
|
Perform the second step of the algorithm again by choosing the next working vertex.
Vertex $A$A
Vertex $B$B
Vertex $C$C
Vertex $D$D
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.
|
|||||||||
|
|
||||||||
|
For each vertex, enter the least weight between itself and vertex $A$A.
$0$0 | ||||
$\editable{}$ | $\editable{}$ | |||
$\editable{}$ |
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.
Use the given label lists to number the vertices in order, according to the algorithm.
|
|||||||||
|
|
||||||||
|
For each vertex, enter the least weight between itself and the starting vertex
$\editable{}$ | ||||
$\editable{}$ | $\editable{}$ | |||
$\editable{}$ |
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.
Using the algorithm, fill in the order (upper box) and label list (lower box) for each vertex.
|
|
|||||||||||
|
|
|||||||||||
|
|
For each vertex, enter the least weight between itself and vertex $A$A.
$\editable{}$ | $\editable{}$ | |||
$\editable{}$ | $\editable{}$ | |||
$\editable{}$ | $\editable{}$ |
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.
Use the given label lists to number the vertices in order, according to the algorithm.
|
|||||||||
|
|
||||||||
|
For each vertex, enter the least weight between itself and the starting vertex
$\editable{}$ | ||||
$\editable{}$ | $\editable{}$ | |||
$\editable{}$ |