Optimisation algorithms revision notes

Purpose

Dijkstra’s shortest path algorithm finds the shortest route from a chosen starting vertex to other vertices in a weighted graph. A path’s length is the total of the edge weights along that path, so the algorithm must compare complete routes rather than just individual edges. Applications include finding routes in road or map systems and selecting efficient routes through communication networks.

Tracing the algorithm

During a trace, keep a tentative distance for each vertex. The starting vertex has distance 0; the other distances are initially treated as unknown or infinitely large. The algorithm repeatedly considers the unprocessed vertex with the smallest tentative distance. It then checks routes from that vertex to its neighbours. If travelling through the current vertex gives a smaller distance, the neighbour’s tentative distance is updated. The selected vertex is then treated as having its shortest distance established.

Worked example

Consider these weighted connections:

• S–A = 4
• S–B = 1
• B–A = 2
• A–C = 1
• B–C = 5
• C–D = 3
• A–D = 7

Start at S. The initial distances are S = 0, A = ∞, B = ∞, C = ∞, and D = ∞. From S, update A to 4 and B to 1. The smallest unprocessed distance is B = 1, so examine routes through B: B–A gives 1 + 2 = 3, improving A from 4 to 3; B–C gives 1 + 5 = 6, so C becomes 6. Next, A = 3 is smallest. Through A, C becomes 3 + 1 = 4, and D becomes 3 + 7 = 10. Next, C = 4 gives D = 4 + 3 = 7, improving it to 7. The resulting shortest route from S to D is S–B–A–C–D, with total length 7.

Common errors

• Choosing the edge with the smallest individual weight instead of comparing total route lengths.
• Forgetting to update a neighbour when a shorter route is discovered.
• Treating a tentative distance as final before the algorithm has selected that vertex.
• Adding edge weights incorrectly when tracing a route.
• Reporting only the final distance when the question asks for the actual path.