Dijkstra’s algorithm finds the shortest path in a weighted graph. Every CS student learns it. What they don’t learn is that vanilla Dijkstra on a continental road graph is too slow to use in production, and fixing that takes some clever preprocessing.

Why Dijkstra Is Too Slow#

Dijkstra explores nodes in order of increasing distance from the source. In the worst case, finding a route from one end of a continent to the other means exploring most of the graph before finding the destination. A road network with 100 million nodes makes this unacceptably slow for real-time routing.

A* improves on Dijkstra by adding a heuristic: an estimate of the remaining distance to the destination (usually straight-line distance). Instead of exploring everything at equal distance, A* prioritizes nodes that are both close to the source and seem close to the destination. Fewer nodes explored, faster answer. The heuristic has to be admissible, meaning it never overestimates, or you lose the correctness guarantee.

Bidirectional search cuts it further: run Dijkstra forward from the source and backward from the destination simultaneously. Stop when the two frontiers meet. You explore roughly half the graph in each direction instead of the full graph in one.

Contraction Hierarchies#

None of these are fast enough for continental routing. Contraction hierarchies preprocess the graph offline to make online queries very fast.

The idea: rank nodes by importance. Motorway junctions are important, side streets are not. Remove unimportant nodes one at a time, adding “shortcut” edges to preserve shortest paths. The remaining graph is much smaller. At query time, only important nodes and their shortcuts are explored.

graph TD A[Full Road Graph - 100M nodes] --> B[Preprocess: Contract Unimportant Nodes] B --> C[Add Shortcut Edges] C --> D[Hierarchical Graph - query only important nodes] D --> E[Bidirectional Query on Hierarchy] style A fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style B fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style C fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style D fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style E fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff

The preprocessing runs offline and takes minutes. Queries on the preprocessed graph run in milliseconds even for continent-scale routes. The trade-off: every time road weights change significantly (major construction, new roads), you need to reprocess.

At Oracle#

I didn’t do routing, but I did dependency resolution in a system with 4000+ service configurations. Finding which services depended on a changed config was essentially a graph search. We tried a recursive SQL query first. It timed out on deep dependency chains. We ended up materializing the transitive closure: precomputing all ancestor-descendant pairs and storing them in a table. Queries became a simple indexed lookup. Same trade-off as contraction hierarchies: offline preprocessing cost, fast online queries.

What I’m Learning#

Routing at scale isn’t an algorithms problem, it’s a preprocessing problem. The algorithm you use at query time is almost an afterthought once the graph structure is optimized.

Have you encountered a graph search problem in your systems that required preprocessing to make it fast?