Shortest paths with Dijkstra’s algorithm
Dijkstra’s algorithm settles vertices in order of their current distance from the start.
Start with distance zero at the source and infinity elsewhere. Select the unsettled vertex with least tentative distance, settle it and update distances to its neighbours. Store predecessors to recover an actual route.
The usual algorithm requires nonnegative edge weights. A minimum spanning tree solves a different problem: connecting all vertices with minimum total weight. Record both the route and its total distance when a shortest-path question asks for them.
Worked example
Edges AB = 4, AC = 1 and CB = 2. Find the shortest route from A to B.
- From A, tentative distances are B = 4 and C = 1.
- Settle C, then update B to 1 + 2 = 3.
- Settle B and recover its predecessor C.
Answer: A → C → B, distance 3
Practise shortest paths with dijkstra’s algorithm
Course mapping
These specification references show where the topic occurs. The questions cover only some parts of each topic.
- 9FM0 · D1 · Decision 1: algorithms on graphs: Shortest paths
- H645 · Y433 · Modelling with algorithms: Shortest paths
- 7367 · discrete · Graphs and algorithms: Shortest paths
- H245 · discrete · Algorithms on graphs: Shortest paths
- 9FM0 · D1 · Decision 1: algorithms on graphs: A minimum spanning tree
- H645 · Y433 · Modelling with algorithms: A minimum spanning tree
- H245 · discrete · Algorithms on graphs: A minimum spanning tree
- H635 · Y413 · N5 Minimum connector problems: A minimum spanning tree
Next practice: Proof by induction.