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 on — describe 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).
What to write in your book
- Set up table: source=0, others=∞.
- Each step: select min unvisited → update neighbours → mark visited.
- Update only if new distance < current 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) | ✓ | ✓ | ✓ | ✓ | ✓ |
Shortest path S→T = 8. Route: trace back T←C←A←B←S, i.e. S→B→A→C→T.
What to write in your book
- Build the table row by row. Update labels when you find shorter paths.
- Trace back path by following which vertex provided each update.
- Final label of destination = shortest path length.
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.
What to write in your book
- Shortest distance from source = final label of destination vertex.
- Trace path: work backwards — find vertex V where label(V) + edge = label(W).
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.