The Toll Road Dilemma

Cheapest route: City 1 → City 3 → City 2 → City 4 → City 5, total cost = 2+1+5+2 = 10 hundred rupees. Direct routes like 1→3→5 (cost 12) or 1→2→4→5 (cost 11) are more expensive. Dijkstra's algorithm finds the optimal path.

Dijkstra's algorithm maintains a set of visited nodes and a table of minimum known distances from the source. At each step, it selects the unvisited node with the smallest tentative distance and updates its neighbours. Step 1: Initialise: dist[1]=0, dist[2]=∞, dist[3]=∞, dist[4]=∞, dist[5]=∞. Unvisited = {1,2,3,4,5}. Step 2: Visit City 1 (dist=0): update neighbours. dist[2] = min(∞, 0+4) = 4. dist[3] = min(∞, 0+2) = 2. Unvisited = {2,3,4,5}. Step 3: Visit City 3 (dist=2, smallest unvisited): update neighbours. dist[2] = min(4, 2+1) = 3. dist[4] = min(∞, 2+8) = 10. dist[5] = min(∞, 2+10) = 12. Unvisited = {2,4,5}. Step 4: Visit City 2 (dist=3, smallest unvisited): update neighbours. dist[4] = min(10, 3+5) = 8. Unvisited = {4,5}. Step 5: Visit City 4 (dist=8, smallest unvisited): update neighbours. dist[5] = min(12, 8+2) = 10. Unvisited = {5}. Step 6: Visit City 5 (dist=10). Algorithm complete. Shortest distance from City 1 to City 5 = 10. Key Insight: Dijkstra's algorithm is greedy — it always extends the currently shortest known path. The key property enabling this: once a node is visited (its shortest path is finalised), no future path through unvisited nodes can improve it, because all edge weights are non-negative. This greedy correctness proof is fundamental to understanding why the algorithm works.