Dijkstra's algorithm
Studying this course? Keep your progress in one place.
Key facts
- Dijkstra's algorithm finds the shortest path from a start vertex to every other vertex. Weights must not be negative.
- Each vertex records its order of labelling, its final label and its working values.
- The smallest working value among unlabelled vertices is made permanent and never changes.
- Find the route by working backwards from the target: label plus edge length equals the label you are at.
- For a route through a vertex, add the shortest distance to it and from it.
What Dijkstra's algorithm does
It finds the shortest distance from one start vertex to all other vertices of a network with non-negative weights.
Dijkstra's algorithm gives routes such as the shortest road distance or least travel time.
Each vertex is a box with four parts:
- the vertex name,
- the order of labelling: 1 for the start, 2 for the next vertex made permanent, and so on,
- the final label: the shortest distance from the start,
- the working values tried and replaced on the way.
A permanent label is fixed once the vertex is chosen.
- Start vertexorder 1, final label 0
- Permanent labelshortest distance, never changes
What order of labelling does the start vertex receive?
The steps
Label the start 0, update working values from the newest label, then make the smallest unlabelled working value permanent. Repeat.
- Give the start vertex permanent label 0 and order 1.
- For each vertex joined to the vertex just labelled, add its label to the edge length. If this is smaller than the current working value (or none exists), record it and cross out the larger one.
- Choose the smallest working value among vertices without a permanent label. Make it permanent and give the next order.
- Repeat steps 2 and 3 until the target (or every vertex) is labelled.
The smallest value is final because any other route must pass through a vertex with a value at least as large.
- 1
Update
add the label to each edge length and record smaller working values
- 2
Choose
pick the smallest working value among unlabelled vertices
- 3
Make permanent
give it the next order of labelling
Then back to step 1
Working values at unlabelled vertices are , , . Which is made permanent next?
A worked example
Work outwards from , always labelling the smallest working value, until is labelled.
Roads: , , , , , , , , . Find the shortest route from to .
The labels give the shortest distance to each vertex. Compare all working values at before stopping.
Worked example
Apply Dijkstra's algorithm from to .
- 1
. Working values , . Smallest is : permanent.
- 2
From : replaces 7; . Smallest is .
- 3
From : replaces 10; . Smallest is .
- 4
From : (not better than 14); . Smallest is .
- 5
From : (not better than 17). is permanent.
Via the distance to is . What happens to this value?
Finding the route
Work backwards from the target: at each vertex pick the neighbour whose label plus the edge length equals the label there.
The labels give the length. To find the route, start at the target and find the neighbour whose final label plus the edge length equals the label you are at.
In the example, so the route comes from . , so from . , so from , and from .
The route is with length 17. Show these sums to justify each step.
For a directed network, only follow arcs in the direction of the arrow.
- Label of earlier vertex edge length = label here
Final labels are , , , , , . Using the example network, which vertex comes just before on the shortest route to ?
Variations
Final labels give every distance, a vertex to call at splits the problem in two, and a closed road means repeating from where it mattered.
The final labels give the shortest distance to every labelled vertex, not just the target.
A vertex's shortest route may leave a long edge unused, so compare all working values at the target before you stop.
Several targets
- Read every final label
Route via X
- Add start-to-X and X-to-target
Road closed
- Redo from where it mattered
Directed
- Follow arrows only
A route must call at . The shortest distance from the start to is 5 and from to the target is 9. What is the length of the shortest such route?
Try an exam question
A network has roads , , , , , , . Use Dijkstra's algorithm to find the shortest distance from to and state the route.
[5 marks]
- [1] is labelled first; working values , .
- [1] is made permanent and improves to .
- [1] is made permanent; working values (via , ) and .
- [1] is made permanent and improves to .
- [1]Shortest distance is 12 by the route .
That's the notes covered.
Carry on to the next subtopic.
Try a question
What is the final label of vertex ?
1 mark, marked against the mark scheme
What is the final label of vertex ?
1 mark, marked against the mark scheme