Graph theory
Lesson 10 of 10
Shortest paths
Objective. Apply Dijkstra's algorithm to a weighted graph.
The key idea
Keep a tentative distance for each vertex, always finalise the smallest unvisited one, then relax its neighbours. It requires non-negative weights.
Worked example
From A: A→B is 2, A→C is 5, B→C is 1. Shortest A to C?
- 1Via A→C directly: 5.
- 2Via A→B→C: 2 + 1 = 3.
- 33 is smaller.
Answer: 3, via B
Practice
Each question comes with a picture and a listen button. Try it first, then reveal the answer.
Common mistake. Finalising a vertex before all shorter routes to it have been considered.
Your progress
Tick each step as you finish it — Continue brings you back here.
0 of 5 steps complete