The weighted graph below shows the distances, in km, between six locations.
Dijkstra's algorithm is used to find the shortest route from A to every other node. At each step, the unfinalised node with the smallest working distance is permanently labelled (finalised), and the working distance of each of its unfinalised neighbours is updated if the route through the finalised node is shorter.
(a) State the order in which the nodes are permanently labelled (finalised). [2]
(b) State the length of the shortest path from A to F. [1]
(c) State the shortest path from A to F. [1]
(d) Explain why the working value for B changes from 4 to 3 during the algorithm. [1]
(e) State one real-world application of Dijkstra's shortest path algorithm. [1]
- (a) A, C, B – first three nodes in the correct order (allow the start node A omitted, i.e. C, B first)(1)
- (a) D, E, F – remaining nodes in the correct order after A, C, B(1)
- (b) 13 km (allow 13 with no units)(1)
- (c) A–C–B–D–E–F(1)
- (d) When C is finalised (distance 2), the route A–C–B gives 2 + 1 = 3, which is less than the direct edge A–B of 4(1)
- (e) Any one valid application, e.g. satellite navigation / route planning (shortest or fastest road route); routing packets across a network (e.g. OSPF / link-state routing); planning shortest delivery or travel routes in logistics or games (pathfinding); finding cheapest flight or rail connections. Must be an application of finding a shortest/least-cost path; reject just ‘finding the shortest path’ with no context(1)
- Answer: (a) A, C, B, D, E, F (b) 13 km (c) A–C–B–D–E–F (d) Going via C gives 2 + 1 = 3, which is less than the direct edge of 4 (e) e.g. satellite navigation (finding the shortest road route) or routing packets through a network.
- Examiner tip: Update a working value only when the new total is smaller, and always finalise the unfinalised node with the smallest working value next.