Try to imagine every possible driving route between New York and San Francisco — the number of combinations explodes astronomically. Yet mapping apps return practical routes in under a second. The secret is not magic but clever algorithms that exploit the structure of road networks and a lot of pre-processing.
Dijkstra’s simple and powerful idea
In 1956 Edsger Dijkstra devised an elegant method to compute shortest paths from one source to all other nodes. It maintains the current best-known distance (cost) to each node and repeatedly explores the unexplored node with the smallest cost, updating neighbors as it goes. Dijkstra is guaranteed to find shortest paths, but on very large graphs (tens of millions of intersections) it can still examine most nodes and take seconds or longer per query.
A* and bidirectional search: more directed exploration
A* improves on Dijkstra by adding a heuristic — typically straight-line distance — to bias the search toward the destination. That reduces explored nodes, especially inside cities, but can be less effective if you optimize for travel time rather than distance. Running searches from both source and target simultaneously (bidirectional search) further halves the explored region in many cases.
Road hierarchies and contraction
Human drivers naturally use a hierarchy: local streets → highways → local streets. Algorithms can encode a similar hierarchy automatically. Contraction hierarchies repeatedly identify “important” nodes (those that split the map) and add shortcut edges so that many low-level routes become single higher-level edges. The result: searches climb the hierarchy and meet near the top, drastically reducing the search space while preserving exact shortest paths.
Preprocessing vs. query time trade-offs
Building contraction hierarchies requires substantial pre-processing and adding shortcut edges, but that work is done once (or periodically when the map changes). After preprocessing, queries run in microseconds on continental graphs — tens of thousands of times faster than a plain Dijkstra run on the same network.
In short, modern routing combines Dijkstra’s core idea with heuristics, bidirectional search and clever pre-processing (like customizable contraction hierarchies). Together these techniques take advantage of road-network structure to produce sub-second, exact routes for millions of simultaneous users.
