Inside the Grid: How Routing Engines Calculate Routes in Milliseconds

Google Maps

Imagine planning a road trip from New York City to San Francisco. To find the absolute fastest route across North America, a computer must navigate a massive network containing over 64 million intersections and a nearly infinite web of connecting roads.

If a computer tried to calculate every possible route using raw brute force, it would have to evaluate roughly 10220 permutations. Even a supercomputer checking a billion routes per second would take longer than the age of the universe to finish.

Yet, the mapping applications we use every day deliver optimal, traffic-adjusted routes across entire continents in just a fraction of a second. Solving this problem isn’t just a triumph of raw hardware power; it is the result of a decades-long evolution in graph theory and network optimisation.

The Foundation: Dijkstra’s Algorithm and Direction-Blindness

Every digital map is mathematically represented as a weighted graph. Intersections and dead-ends are nodes, the roads connecting them are edges, and the travel times or physical distances are weights.

In 1956, computer scientist Edsger Dijkstra designed the foundational framework for solving this problem: Dijkstra’s Algorithm.

[Origin Node (Cost: 0)] ---> [Neighbor A (Cost: 3)] ---> [Neighbor B (Cost: 7)]
                       ---> [Neighbor C (Cost: 5)]

Dijkstra’s approach operates like a ripple in a pond:

• It assigns a cost of zero to the starting node and infinity to all other nodes.
• It evaluates every neighbouring road, updating its tentative travel costs.
• It continuously shifts focus to the unexplored node with the lowest cumulative cost, building out a tree of shortest paths.

Because it systematically explores outward from the lowest to the highest cost, Dijkstra’s algorithm mathematically guarantees finding the absolute shortest path. However, it possesses a massive flaw: it is completely direction-blind.

If you attempt to route a vehicle across a city, Dijkstra’s algorithm will explore miles in the exact opposite direction of your destination simply because those roads have a low cumulative cost. On a continental scale, a well-tuned Dijkstra search takes roughly 7 seconds and forces a server to evaluate almost all 64 million nodes, an unsustainable bottleneck when millions of users query a system simultaneously.

The Directed Search Paradox

To fix this direction blindness, computer scientists introduced the A* (A-Star) search algorithm* in 1968. A introduces a heuristic,** a smart mathematical estimate to guide the search frontier.

By using the geographical coordinates of nodes, A calculates the straight-line distance directly to the destination. It then prioritises exploring nodes based on their actual cost from the origin plus* the estimated remaining distance to the target. This forces the search frontier to tunnel aggressively toward the destination rather than expand in a massive circle.

Dijkstra Search Frontier:       A* Search Frontier:
       ______                         __
     /        \                     /    \
    |   Start  |                   | Start ====> Destination
     \________/                     \__/

While A* works flawlessly when minimising physical distance, it breaks down when routing engines optimise for travel time.

When calculating the fastest route, speed limits and traffic variability make straight-line distance a massive underestimate of time. Furthermore, calculating complex coordinate heuristics on the fly requires intensive mathematical operations (such as square roots) for every node. On massive networks optimising for time, A* frequently evaluates more nodes and runs slower than a highly optimised, baseline Dijkstra search.

Exploiting Network Topology: Road Hierarchies

Human drivers do not plan long-distance trips by assessing every local side street between two cities. Instead, we use a natural structural hierarchy: we navigate local roads to reach a highway, cruise on major interstate networks for the bulk of the journey, and drop back down to local streets at our destination.

Early in-car navigation systems in the 1990s tried to replicate this behaviour using manual hierarchies. Map engineers manually tagged roads into tiers (e.g., freeways, major arterials, local streets). Systems would then run a Bidirectional Dijkstra search, exploring simultaneously from both the start and end points to meet in the middle while aggressively filtering out low-tier roads as the search moved away from the origin.

However, manual hierarchies lack mathematical guarantees. If a local road sequence or an unclassified bypass happens to be faster than the highway due to an obstruction, the rigid hierarchical filters will completely miss it, returning a sub-optimal route.

Modern Scalability: Customizable Contraction Hierarchies

To achieve millisecond-level query speeds without sacrificing mathematical accuracy, modern industrial routing engines rely on an automated, multi-phase pre-processing architecture known as Customizable Contraction Hierarchies (CCH).

Instead of human mapmakers manually guessing which roads are important, CCH uses advanced graph decomposition techniques to mathematically re-engineer the road network before a user ever asks for directions.

Phase 1: Nested Dissection (Node Ranking)

The algorithm automatically analyses the graph topology to identify critical geographic bottlenecks known as “small cuts” that split the network in half.

For instance, to drive from the East Coast to the West Coast of the United States, a vehicle must cross one of only 102 bridges spanning the Mississippi River. Because millions of cross-continental routes are forced to pass through this tiny bottleneck, these 102 bridge nodes are assigned the highest topological rank in the entire network.

The algorithm then recursively cuts the remaining network segments in half, ranking every single intersection down to minor residential cul-de-sacs.

[Low Rank: Cul-de-sac] ---> [Medium Rank: Major Arterial] ---> [High Rank: Continental Bridge]

Phase 2: Graph Contraction and Shortcuts

To bypass millions of low-tier nodes during a live search, the algorithm mathematically “contracts” the graph from the bottom up.

If a sequence travelling through a series of low-ranked local streets represents the fastest path between two higher-ranked intersections, the system creates a pre-computed shortcut edge directly connecting those high-ranked nodes. This shortcut stores the precise, pre-calculated travel cost of the underlying local roads, allowing the routing engine to completely ignore the side streets during a live query.

Standard Path:  [Node A (High)] ---> [Node B (Low)] ---> [Node C (High)]
                                      \_______________/
Shortcut Edge:  [Node A (High)] =======================> [Node C (High)]

Phase 3: The Three-Phase Query Execution

When real-world conditions like traffic accidents, construction, or changing speed limits occur, managing a massive network requires splitting the computation into three highly efficient phases:

• Topological Pre-processing (Metric-Independent): The graph is ordered, and shortcuts are generated based purely on the shape of the roads. This step can take over an hour but only happens when physical infrastructure changes (like a new bridge opening).
• Customisation (Metric-Dependent): Live traffic data feeds into the system, and the weights of the pre-computed shortcuts are refreshed. Because the structural shortcuts already exist, this mathematical update takes less than a single second across the entire network.
• The Upward Search: When a user requests a route, a bidirectional search is executed. Because of the pre-computed structure, the algorithm is strictly restricted to only exploring upward to higher-ranked nodes.

[High-Rank Continental Backbone]
                       ^          ^
                      /            \  (Search meets in the middle)
                     /              \
     [Origin Cluster]                [Destination Cluster]

Instead of sweeping across millions of irrelevant local intersections across mid-America, a search from San Francisco to Montreal only evaluates a tiny cluster of local roads around the origin, immediately jumps onto the pre-computed high-level highway backbone, and exits through a small cluster at the target destination.

The Efficiency Frontier

By shifting the heavy mathematical heavy-lifting into automated, traffic-customizable pre-processing, modern routing engines alter the computational reality of pathfinding.

Routing Approach | Average Nodes Evaluated | Average Query Runtime

Standard Dijkstra | ~64,000,000 nodes | ~7 seconds

Contraction Hierarchies (CCH) | ~1,450 nodes | ~200 microseconds (≈ 0.2 milliseconds)

This structural optimisation yields an algorithm that operates roughly 35,000 times faster than pure Dijkstra’s algorithm while maintaining absolute mathematical accuracy. It ensures that regardless of concurrent server loads or real-time traffic updates, navigation systems can parse continental geography instantly.

While modern routing engines rely on complex multi-phase architectures, advanced data pipelines, and real-time traffic customisation, their core computational engine remains remarkably unchanged. Underneath the layers of shortcuts, hierarchical node contractions, and bidirectional searches beats the heart of a 70-year-old algorithm.

Danish computer scientist Mikkel Thorup noted that virtually all theoretical and practical developments in single-source shortest path algorithms continue to be built directly upon the foundation laid by Edsger Dijkstra. From the early variants of in-car navigation to today’s massive cloud-based Customizable Contraction Hierarchies, every breakthrough borrows pieces of his elegant logic.

Dijkstra famously believed that “simplicity is a prerequisite for reliability.” He conceptualised his foundational algorithm during a brief 20-minute coffee break in 1956, designing it entirely without a pen and paper to force himself to avoid all avoidable complexities. Today, that commitment to elegant simplicity is precisely what allows global network infrastructure to scale. Every time a routing engine instantly maps a path across a continent, it stands as a testament to Dijkstra’s enduring legacy, proving that the most powerful solutions are often the ones built on a foundation of pure, unadulterated simplicity.