Shortest Paths, Dijkstra's Algorithm
Uber's routing system uses a variant of Dijkstra's algorithm to find the fastest path from a driver to a passenger across Sydney's road network in under 50 milliseconds. This lesson teaches you the systematic table method that makes finding shortest paths reliable, even on exam diagrams with 6+ vertices.
Practise this lesson
Three printable worksheets that build from foundations to mastery, or build your own from any module’s questions.
A delivery driver needs the shortest route from depot (S) to destination (T). The weighted directed network has 5 intermediate stops. How would you find the shortest path, not just guess?
Before reading ondescribe your strategy.
Dijkstra's algorithm finds the shortest path from a source to all other vertices. It always selects the unvisited vertex with the smallest known distance, a "greedy" strategy that is provably optimal for non-negative weights.
Distance label: the current known shortest distance from the source to each vertex. Initially: source = 0, others = ∞.
Visited / Permanent: once a vertex's distance is confirmed (it is the smallest unvisited), it is marked permanent.
Update rule: when visiting vertex V, for each neighbour W: if dist(V) + weight(V→W) < dist(W), update dist(W).
Result: after all vertices are visited, the distance labels give the shortest path lengths from the source.
Key facts
- Dijkstra's finds shortest path from source
- Initial labels: source=0, others=∞
- Select minimum unvisited each step
Concepts
- Why greedy strategy works here
- Difference between distance and path
- How to update labels correctly
Skills
- Complete a Dijkstra's table step by step
- Find shortest path length between two vertices
- Trace back the actual shortest route
Set up: Create a table with a row for each step and a column for each vertex. Initialise: source vertex = 0, all others = ∞.
Each iteration:
- Select the unvisited vertex with the smallest current label. Circle it (it is now permanent).
- For each unvisited neighbour of that vertex: calculate new distance = current vertex label + edge weight.
- If this new distance is less than the neighbour's current label, update the label.
- Move to next row in the table and repeat.
Stop: when all vertices are visited (or when the destination is made permanent).
Dijkstra’s algorithm finds shortest paths from one source to all other vertices. Set up a table (rows = steps, columns = vertices). Source = 0, others = ∞. Each iteration: select the unvisited vertex with the smallest current label, update neighbours.
Pause, copy Dijkstra's table setup (columns = all vertices; source = 0, others = infinity; rows = iteration steps) and the iteration rule: select the unvisited vertex with the current minimum label; update each unvisited neighbour's label if (current label + edge weight) is less than the existing label into your book.
We just saw Dijkstra's algorithm setup, source label = 0, all others = infinity, and the general iteration logic: select the unvisited vertex with the current minimum label, then update its neighbours. That raises a question: the algorithm loops through multiple iterations, exactly what happens at each step to update the table? This card answers it → at each step, visit the minimum-label unvisited vertex; for each unvisited neighbour, calculate: current label + edge weight; update the neighbour's label only if this new value is smaller than the existing label.
Network: vertices S, A, B, C, T. Edges: S→A(4), S→B(2), A→C(3), A→T(6), B→A(1), B→C(5), C→T(2).
Step-by-step table:
| Step | Vertex visited | S | A | B | C | T |
|---|---|---|---|---|---|---|
| Init | 0* | ∞ | ∞ | ∞ | ∞ | |
| 1 | S (0) | ✓ | 4 | 2 | ∞ | ∞ |
| 2 | B (2) | ✓ | 3 | ✓ | 7 | ∞ |
| 3 | A (3) | ✓ | ✓ | ✓ | 6 | 9 |
| 4 | C (6) | ✓ | ✓ | ✓ | ✓ | 8 |
| 5 | T (8) | ✓ | ✓ | ✓ | ✓ | ✓ |
Dijkstra’s table method: at each step, visit the vertex with the current minimum label. Update adjacent unvisited vertices: new label = current label + edge weight, only if smaller than the existing label. Circle finalized labels, they never change once set.
Pause, copy the update rule (only update a vertex's label if the new path is shorter, never increase a label) and the finalised-label rule (once a vertex is selected as the minimum, its label is finalised and never changes) into your book.
Shortest path S→T = 8. Route: trace back T←C←A←B←S, i.e. S→B→A→C→T.
We just saw working through Dijkstra's table, selecting the minimum unvisited vertex at each iteration and updating neighbours only when a shorter path is found. That raises a question: the completed table gives a final label for each vertex, how do you read the actual shortest path (the sequence of vertices), not just the shortest distance? This card answers it → work backwards from the destination: at each vertex, find the predecessor whose label + the edge weight to the current vertex equals the current vertex's label; trace back to the source.
Once Dijkstra's completes:
- The final label of each vertex = shortest distance from source to that vertex.
- To find the actual path: work backwards from destination. At each vertex, find which predecessor provided the shortest distance.
- For vertex W with label d: look for a vertex V where label(V) + weight(V→W) = d. V was on the shortest path to W.
C has label 6. A→C has weight 3; A has label 3; 3+3=6 ✓ → A precedes C.
A has label 3. B→A has weight 1; B has label 2; 2+1=3 ✓ → B precedes A.
B has label 2. S→B has weight 2; S has label 0; 0+2=2 ✓ → S precedes B.
Path: S→B→A→C→T, length 8.
After Dijkstra’s completes: the final label at each vertex = shortest distance from source. To find the actual path: work backwards from the destination, at each step finding the vertex whose label + edge weight = current vertex’s label.
Pause, copy the path-tracing rule: work backwards from the destination; at each step, find the vertex whose finalised label plus the edge weight to the current vertex equals the current vertex's label, that vertex is the predecessor; follow the chain back to the source into your book.
Worked examples · reveal each step
Network: S, A, B, C. Edges: S→A(5), S→B(3), A→C(4), B→A(2), B→C(8). Find shortest distances from S to all vertices.
Using the result from Problem 1 (S=0, A=5, B=3, C=9): find the shortest path from S to C and state the route.
A delivery network has towns A, B, C, D, E with travel times (min): A→B(8), A→C(3), B→D(6), C→B(2), C→D(9), D→E(4). Find the shortest time from A to E.
Route: A→C→B→D→E (0+3+2+6+4=15 min).
- Network: S→A(6), S→B(4), A→C(3), B→A(1), B→C(7), C→T(2), A→T(8). Use Dijkstra's to find shortest S to T.
- At step 2 in Dijkstra's, you visit vertex B with label 4. Neighbour A has current label 6 and edge B→A has weight 1. Do you update A? Why?
- A student finishes Dijkstra's and says "the shortest path to T is 12." Another student traces back and finds the route S→C→T with length 12. How are these two answers related?
- Why must Dijkstra's algorithm NOT be used when a network has negative-weight edges?
Dijkstra's systematic table method guarantees the shortest path, not just a short one. The "always extend the nearest unvisited" strategy is provably optimal. Did your initial strategy match this approach?
Q1. In Dijkstra's algorithm, the source vertex is initially assigned a distance label of:
Q2. At each step of Dijkstra's algorithm, you select:
Q3. Dijkstra's algorithm updates a neighbour's label when:
Q4. After Dijkstra's algorithm completes, the final label of a vertex represents:
Q5. To find the actual shortest route (not just the distance) after Dijkstra's, you should:
SA 1. Network: A→B(7), A→C(2), B→D(3), C→B(4), C→D(9), D→E(1). Use Dijkstra's algorithm starting at A to find the shortest distance to E. Show the table. (3 marks)
SA 2. A student is running Dijkstra's and makes vertex C permanent with label 8. Later, they find a path to C with total weight 7. What error did the student make, and what should the correct procedure be? (2 marks)
Answers (click to reveal)
MC 1, A: Source = 0.
MC 2, C: Select minimum unvisited each step.
MC 3, B: Update when shorter path found.
MC 4, D: Final label = shortest distance from source.
MC 5, B: Traceback from destination.
SA 1 (3): Correct table setup [1]; correct updates [1]; final answer E=10 and route A→C→B→D→E [1].
SA 2 (2): Error identified: made permanent before checking all unvisited [1]; correct procedure stated [1].
Timed questions on Dijkstra's algorithm. Gold tier requires completing the full table correctly under time pressure.
⚔ Enter the arenaMark lesson as complete
Tick when you've finished. This completes the MS-N2 network concepts unit.