Solve shortest-path problems by inspection or Dijkstra’s algorithm.
Key skillsSolve shortest-path problems by inspection or Dijkstra’s algorithm.
The study design publishes this in the combined Units 3–4 list; the stated content applies to Unit 4.
Build the idea
Dijkstra’s algorithm progressively finalises the smallest tentative distance from a starting vertex. Each finalisation tests whether travelling through that vertex improves neighbouring distances. Record predecessors as well as distances so a route can be reconstructed. The standard procedure assumes non-negative edge weights; an unreachable vertex keeps infinite distance rather than receiving an invented route.
Try the sample task
Run Dijkstra from A on the undirected network AB=4, AC=2, BC=1, BD=5, CD=7, CE=3, ED=1. Show finalised vertices and any changed tentative distances.
The full worksheet includes the worked solution and remaining task set.
What this activity covers
This focused activity develops the stated idea through one context. It is practice, not evidence that every application or subclause of a broad study-design bullet has been mastered.