Dijkstra's algorithm is a series of steps used to determine the shortest path between two nodes in a graph.
This algorithm was created by a dutch computer scientist, Edsger Dijkstra.
Example
Question 2 from the VCAA 2018 Further Mathematics examination 1
Niko drives from his home to university. The network below shows the distances, in kilometres, along a series of streets connecting Niko’s home to the university. The vertices A, B, C, D and E represent the intersection of these streets.
The shortest path for Niko from his home to the university could be found using Dijkstra's algorithm.
Step 1 Draw a table with 7 columns (the number of vertices) and fill in the headings as shown below.
| A | B | C | D | E | university | |
| home |
Step 2 Write the direct distances between home and vertices A and C as shown in the table below.
| A | B | C | D | E | university | |
| home | 2 | - | 3 | - | - | - |
Step 3 Select the smallest number in the row: 2. This number will stay selected until the end.
| A | B | C | D | E | university | |
| home | 2 | - | 3 | - | - | - |
Step 4 Add another row to the table. Since the smallest number is at A, then write A + 2 as the label of the next row.
| A | B | C | D | E | university | |
| home | 2 | - | 3 | - | - | - |
| A + 2 | 2 |
Step 5 Write the direct distances (+ 2) from vertex A to vertices B, C and D as shown in the table below.
| A | B | C | D | E | university | |
| home | 2 | - | 3 | - | - | - |
| A + 2 | 2 | 4 + 2 = 6 | 2 + 2 = 4 | 2 + 2 = 4 | - | - |
Note
In the C column 4 > 3. In such situations we keep the smallest number. Therefore, the values will be as shown in the table below.
| A | B | C | D | E | university | |
| home | 2 | - | 3 | - | - | - |
| A + 2 | 2 | 6 | 3 | 4 | - | - |
Step 6 Select the smallest number in the row that has not been selected before: 3. This number will stay selected until the end.
| A | B | C | D | E | university | |
| home | 2 | - | 3 | - | - | - |
| A + 2 | 2 | 6 | 3 | 4 | - | - |
Step 7 Add another row to the table. Since the smallest number is at C, then write C + 3 as the label of the next row.
| A | B | C | D | E | university | |
| home | 2 | - | 3 | - | - | - |
| A + 2 | 2 | 6 | 3 | 4 | - | - |
| C + 3 | 2 | 3 |
Step 8 Write the direct distance (+ 3) from vertex C to vertex E and keep all the other values as they are.
| A | B | C | D | E | university | |
| home | 2 | - | 3 | - | - | - |
| A + 2 | 2 | 6 | 3 | 4 | - | - |
| C + 3 | 2 | 6 | 3 | 4 | 4 | - |
Step 9 Select the smallest number in the row that has not been selected before: 4. This number will stay selected until the end.
Note
Choose either D or E; the final answer will be the same.
| A | B | C | D | E | university | |
| home | 2 | - | 3 | - | - | - |
| A + 2 | 2 | 6 | 3 | 4 | - | - |
| C + 3 | 2 | 6 | 3 | 4 | 4 | - |
Step 10 Add another row to the table. Since the smallest number is at D, then write D + 4 as the label of the next row.
| A | B | C | D | E | university | |
| home | 2 | - | 3 | - | - | - |
| A + 2 | 2 | 6 | 3 | 4 | - | - |
| C + 3 | 2 | 6 | 3 | 4 | 4 | - |
| D + 4 | 2 | 3 | 4 |
Step 11 Write the direct distance (+ 4) from vertex D to university and keep all the other values as they are.
| A | B | C | D | E | university | |
| home | 2 | - | 3 | - | - | - |
| A + 2 | 2 | 6 | 3 | 4 | - | - |
| C + 3 | 2 | 6 | 3 | 4 | 4 | - |
| D + 4 | 2 | 6 | 3 | 4 | 4 | 7 |
Step 12 Select the smallest number in the row that has not been selected before: 4. This number will stay selected until the end.
| A | B | C | D | E | university | |
| home | 2 | - | 3 | - | - | - |
| A + 2 | 2 | 6 | 3 | 4 | - | - |
| C + 3 | 2 | 6 | 3 | 4 | 4 | - |
| D + 4 | 2 | 6 | 3 | 4 | 4 | 7 |
Step 13 Add another row to the table. Since the smallest number is at E, then write E + 4 as the label of the next row.
| A | B | C | D | E | university | |
| home | 2 | - | 3 | - | - | - |
| A + 2 | 2 | 6 | 3 | 4 | - | - |
| C + 3 | 2 | 6 | 3 | 4 | 4 | - |
| D + 4 | 2 | 6 | 3 | 4 | 4 | 7 |
| E + 4 | 2 | 3 | 4 | 4 |
Step 14 Write the direct distance (+ 4) from vertex E to university and keep all the other values as they are.
| A | B | C | D | E | university | |
| home | 2 | - | 3 | - | - | - |
| A + 2 | 2 | 6 | 3 | 4 | - | - |
| C + 3 | 2 | 6 | 3 | 4 | 4 | - |
| D + 4 | 2 | 6 | 3 | 4 | 4 | 7 |
| E + 4 | 2 | 6 | 3 | 4 | 4 | 5 + 4 = 9 |
Note
In the university column 9 > 7. In such situations we keep the smallest number. Therefore, the values will be as shown in the table below.
| A | B | C | D | E | university | |
| home | 2 | - | 3 | - | - | - |
| A + 2 | 2 | 6 | 3 | 4 | - | - |
| C + 3 | 2 | 6 | 3 | 4 | 4 | - |
| D + 4 | 2 | 6 | 3 | 4 | 4 | 7 |
| E + 4 | 2 | 6 | 3 | 4 | 4 | 7 |
Step 15 Select the smallest number in the row that has not been selected before: 6. This number will stay selected until the end.
| A | B | C | D | E | university | |
| home | 2 | - | 3 | - | - | - |
| A + 2 | 2 | 6 | 3 | 4 | - | - |
| C + 3 | 2 | 6 | 3 | 4 | 4 | - |
| D + 4 | 2 | 6 | 3 | 4 | 4 | 7 |
| E + 4 | 2 | 6 | 3 | 4 | 4 | 7 |
Step 16 Add another row to the table. Since the smallest number is at B, then write B + 6 as the label of the next row.
| A | B | C | D | E | university | |
| home | 2 | - | 3 | - | - | - |
| A + 2 | 2 | 6 | 3 | 4 | - | - |
| C + 3 | 2 | 6 | 3 | 4 | 4 | - |
| D + 4 | 2 | 6 | 3 | 4 | 4 | 7 |
| E + 4 | 2 | 6 | 3 | 4 | 4 | 7 |
| B + 6 | 2 | 6 | 3 | 4 | 4 |
Step 17 Write the direct distance (+ 6) from vertex B to university and keep all the other values as they are.
| A | B | C | D | E | university | |
| home | 2 | - | 3 | - | - | - |
| A + 2 | 2 | 6 | 3 | 4 | - | - |
| C + 3 | 2 | 6 | 3 | 4 | 4 | - |
| D + 4 | 2 | 6 | 3 | 4 | 4 | 7 |
| E + 4 | 2 | 6 | 3 | 4 | 4 | 7 |
| B + 6 | 2 | 6 | 3 | 4 | 4 | 6 + 2 = 8 |
Note
In the university column 8 > 7. In such situations we keep the smallest number. Therefore, the values will be as shown in the table below.
| A | B | C | D | E | university | |
| home | 2 | - | 3 | - | - | - |
| A + 2 | 2 | 6 | 3 | 4 | - | - |
| C + 3 | 2 | 6 | 3 | 4 | 4 | - |
| D + 4 | 2 | 6 | 3 | 4 | 4 | 7 |
| E + 4 | 2 | 6 | 3 | 4 | 4 | 7 |
| B + 6 | 2 | 6 | 3 | 4 | 4 | 7 |
The shortest path from home to university is 7 km.
To determine the path start from the end, 7.
Move up until the last 7. Since this 7 is in row D, move to the left and stop in column D.
Move up until the last 4. Since this 4 is in row A, move to the left and stop in column A.
Move up until the last 2. Since this 2 is in row home, stop.
The shortest path is: home - A - D - university.
