Dijkstra's algorithm
Studying this course? Keep your progress in one place.
Key facts
- Dijkstra's algorithm finds the shortest distance from a start vertex to every vertex of a network with positive weights.
- Each vertex has a box with the order of labelling, the final value and the working values.
- A new working value is the final value of the vertex just labelled plus the arc weight; keep it only if it is smaller.
- Find the route by back-tracking: final value of vertex − arc weight = final value of the previous vertex.
- You can stop as soon as the target is permanently labelled.
The shortest path problem
The shortest path problem asks for the path between two vertices with the least total weight. Dijkstra's algorithm solves it by labelling vertices in order of increasing distance.
In a network each arc has a weight, such as a distance, time or cost. The shortest path problem asks for the path between two vertices of least total weight.
Trying every path becomes impractical as the network grows, so we use Dijkstra's algorithm.
It works from a start vertex, finds the shortest distance to every vertex, and works for any network with positive weights. It can stop once the target is permanently labelled.
When can you stop Dijkstra's algorithm if you only need the distance to one target vertex?
The algorithm step by step
Label the start vertex 0, update the working values of its neighbours, make the smallest working value permanent, and repeat until the target is labelled.
Give each vertex a box with three parts: the order of labelling, the final value and the working values.
Working values that are replaced by smaller ones are crossed out but kept, so the working can be checked.
- 1
Start
give the start vertex order 1 and final value 0
- 2
Update neighbours
final value + arc weight; keep it if smaller than the working value there
- 3
Choose
take the smallest working value not yet permanent; make it final and give it the next order number
- 4
Repeat
update and choose until the target is labelled
- New working valuefinal value just labelled + arc weight
Which value do you add the arc weight to when updating a neighbouring vertex?
Worked example
Starting at S, B becomes permanent at 2, then A at 3 by going via B, then T at 9.
Take the network above with arcs , , , and .
Work through the labelling in order. The working value is replaced by 3 when a shorter route via is found, and is replaced by 9 via .
- 1
S = 0 (order 1)
the start
- 2
B = 2 (order 2)
the smallest working value after S
- 3
A = 3 (order 3)
via B: 2 + 1 = 3, replacing 4
- 4
T = 9 (order 4)
via A: 3 + 6 = 9, replacing 10
| S | B | A | T | |
|---|---|---|---|---|
| Order of labelling | 1 | 2 | 3 | 4 |
| Final value | 0 | 2 | 3 | 9 |
| Working values | none | 2 | 4, 3 | 10, 9 |
S
- Order of labelling:
- 1
- Final value:
- 0
- Working values:
- none
B
- Order of labelling:
- 2
- Final value:
- 2
- Working values:
- 2
A
- Order of labelling:
- 3
- Final value:
- 3
- Working values:
- 4, 3
T
- Order of labelling:
- 4
- Final value:
- 9
- Working values:
- 10, 9
Worked example
Use Dijkstra's algorithm to find the shortest distance from to .
- 1
Start at with final value (order 1).
- 2
From : working values and . The smallest is , so is permanent (order 2).
- 3
From : , replacing ; . The smallest is , so is permanent (order 3).
- 4
From : , replacing . is the only vertex left, so it is permanent (order 4).
In the example, why is replaced by ?
Finding the route
Work backwards from the target: move to a neighbour whose final value equals the vertex's final value minus the arc weight.
The final values give the length, but you must also give the route. Work backwards from the target. At each vertex, choose the neighbour for which the final value of the vertex minus the arc weight equals the final value of the neighbour.
Write the route from the start to the target, with its total length.
- 1
T = 9
9 − 6 = 3 = A, so go to A
- 2
A = 3
3 − 1 = 2 = B, so go to B
- 3
B = 2
2 − 2 = 0 = S, so the start is reached
- Final value of vertex − arc weight= final value of neighbour
Back-tracking in the worked example
Find the route from to .
- 1
From : , so go to .
- 2
From : , so go to .
- 3
From : , so we have reached the start.
A vertex has final value and is joined to by an arc of weight . has final value . Is on the shortest route to ?
Updating and checking
If a road closes, remove the arc and repeat. A new arc of weight helps only if is less than the current shortest length.
If a road is closed, remove that arc and repeat the algorithm. Any vertex whose shortest route did not use that arc keeps its final value.
If a new arc of weight joins and , it improves the route only when the new total is less than the current shortest length. Here is the shortest distance, found from the algorithm. This gives an inequality for .
Checks: final values increase in order of labelling.
- New arc improves route when current length
In the worked example the shortest length is . A new arc of weight joins directly to . For what values of is the shortest route improved?
Try an exam question
A network has arcs SA = 6, SB = 4, AB = 1, AT = 9, BC = 7 and CT = 2. Use Dijkstra's algorithm to find the shortest route from S to T and state its length.
[4 marks]
- [1]S is 0, and B = 4 is made permanent as the smallest working value.
- [1]From B: A = 4 + 1 = 5 replaces 6, and C = 4 + 7 = 11.
- [1]A = 5 then C = 11 are made permanent; T = 14 via A is replaced by 13 via C.
- [1]Back-tracking gives the route S-B-C-T, with length 13.
That's the notes covered.
Carry on to the next subtopic.
Try a question
Which vertex is permanently labelled third, counting as the first?
1 mark, marked against the mark scheme
Which vertex is permanently labelled third, counting as the first?
1 mark, marked against the mark scheme