The Algorithm That Powers Every GPS
Edsger Dijkstra conceived his shortest-path algorithm in 1956 while sitting at a café in Amsterdam, working it out in about twenty minutes on paper. Published in 1959, it became one of the most widely used algorithms in computer science — the backbone of GPS navigation, network routing protocols like OSPF, and countless logistics systems. Its elegance lies in a simple greedy principle: always expand the closest unvisited node.
How Dijkstra's Algorithm Works
The algorithm maintains a set of visited nodes and a priority queue of tentative distances. Starting from the source node with distance zero, it repeatedly extracts the nearest unvisited node, marks it as permanent, and updates the distances of its neighbours. This 'relaxation' step ensures that when a node is dequeued, its recorded distance is optimal. The process continues until the target is reached or all reachable nodes are visited.
Correctness and Limitations
Dijkstra's correctness depends on one critical assumption: all edge weights must be non-negative. If a negative-weight edge exists, a node that was already finalized might later be reachable via a shorter path, violating the greedy invariant. For graphs with negative weights, Bellman-Ford provides a correct alternative at higher computational cost. For unweighted graphs, a simple BFS suffices.
From Theory to Practice
Modern routing engines like those in Google Maps don't run vanilla Dijkstra on the entire road network. They use hierarchical preprocessing techniques — contraction hierarchies, hub labelling, and A* with landmark heuristics — that answer continental-scale queries in microseconds. Yet every one of these advanced methods builds on Dijkstra's foundational insight: expand outward from the source in order of increasing distance.