How GPS Finds Your Route in Milliseconds

The Impossible Math Behind Every Navigation Request

Every time you ask Google Maps for directions, your phone quietly solves one of the hardest problems in computer science — in about four seconds. That sounds impressive until you realise just how staggering the underlying complexity is. The North American road network alone contains over 64 million intersections, producing somewhere in the region of 10²²⁰ possible routes between any two points. If you could evaluate a billion routes per second, exhaustively checking all of them would still take longer than the current age of the universe — by an almost incomprehensible margin.

And yet, your phone does it while you're still fumbling for your seatbelt. How? The answer is a chain of increasingly clever algorithms, each one building on the last, stretching from a café in Amsterdam in 1956 to the server farms powering modern navigation. Understanding that chain doesn't just satisfy curiosity — it reveals how computer scientists think about hard problems, and why the right data structure can be worth more than a thousand processors.

Dijkstra's Algorithm: The 20-Minute Invention That Changed Everything

In 1956, Dutch mathematician Edsger Dijkstra was trying to demonstrate the practical value of ARMAC, one of the Netherlands' earliest computers, to a public that largely considered computers useless toys. He needed a problem that any non-mathematician could understand instantly. During a shopping trip in Amsterdam, sitting at a café with his fiancée, he found it: what is the shortest route between two cities?

His solution — designed entirely in his head, without pencil or paper — is now known as Dijkstra's algorithm. The elegance is worth unpacking properly.

Imagine a map as a graph: cities are nodes, roads are edges, and each edge carries a weight representing the distance. Dijkstra starts at the source node and assigns every other node a tentative cost of infinity, because nothing has been explored yet. Then it begins expanding outward, always choosing the unexplored node with the lowest known cost. At each step, it asks: does this new path to a neighbouring node beat the cost we already have recorded? If yes, update it. If no, move on.

The crucial insight is this: once a node has been selected as the lowest-cost unexplored node and marked as finalised, you are guaranteed its recorded cost is the true shortest path. Why? Because every unexplored path has an equal or higher cost. Any route that could beat it would have already surfaced during earlier iterations. The algorithm doesn't just find a short path — it proves optimality at each step.

Dijkstra debuted it at ARMAC's inauguration, asking audience members to name two cities on a simplified Dutch map. The machine printed the optimal route town by town, perfectly. His write-up sat in a drawer for three years before finding a home in Numerische Mathematik, a brand-new German journal in 1959. Within years, it had been translated and referenced across management science literature. Dijkstra later recalled finding his name attached to a method in a German textbook — Das Dijkstra'sche Verfahren — with what he described as great amazement.

For a 20-minute invention designed without a single scrap of paper, it held up remarkably well.

Why Dijkstra Alone Can't Power Google Maps

Dijkstra's algorithm is provably optimal and genuinely fast for small graphs. A well-implemented version can route across New York City in under 100 milliseconds. But scale matters enormously here.

On the full North American road network, a well-tuned Dijkstra takes around seven seconds per query. That might seem acceptable — until you remember that Google Maps isn't serving one request at a time. It's handling millions of simultaneous queries. To keep response times under two seconds for all those users, the underlying algorithm needs to resolve in under one millisecond. That means finding a solution roughly 7,000 times faster than Dijkstra alone can manage.

The core inefficiency is directional blindness. Dijkstra expands outward in every direction simultaneously, like a ripple in a pond. If you're routing from Newark Airport to the Central Park Zoo, Dijkstra dutifully explores large chunks of New Jersey and Staten Island before converging on the target — places that are obviously irrelevant to any sensible route. It has no concept of where it should be looking.

A-Star and the Power of Informed Search

The first major improvement is A-star (A*), which gives Dijkstra a sense of direction. The idea is mathematically simple but practically powerful: instead of ordering nodes purely by their cost from the source, A-star orders them by cost plus a heuristic estimate of the remaining distance to the target.

The most natural heuristic is straight-line (Euclidean) distance. If a node is 30 kilometres from your destination as the crow flies, that's the minimum possible remaining cost — you can't travel less than the straight line. By adding this estimate to the known path cost, A-star heavily penalises nodes that are moving away from the target, while nodes heading toward it get priority.

Visually, this transforms the search from an expanding circle into something more like a directed beam. In practical tests routing from Newark to the Central Park Zoo, A-star explored around 7,000 nodes compared to over 65,000 for standard Dijkstra — nearly a 10-fold reduction. This is why A-star is the algorithm of choice for game AI: it's the reason Minecraft mobs navigate around obstacles without wandering aimlessly into lava.

But A-star has a critical weakness for real-world navigation: travel time. When you optimise for speed rather than distance, the straight-line heuristic becomes an extreme underestimate, because speed limits vary wildly across road types. A-star ends up exploring nearly as many nodes as Dijkstra anyway, while also performing expensive square-root calculations to compute heuristic values for every node it touches. On large time-weighted graphs, a well-tuned Dijkstra can actually outperform A-star — a counterintuitive result that highlights how sensitive algorithm performance is to problem framing.

Bidirectional Search and Road Hierarchies

Two further innovations move the needle significantly. The first is bidirectional search: run Dijkstra simultaneously from both the source and the target, stopping when the two frontiers meet in the middle. If a single Dijkstra search covers a circle of radius R, two half-searches each cover a circle of radius R/2. Since area scales with the square of the radius, two half-circles cover roughly half the total area of one full circle. In practice, on a New York City graph, bidirectional Dijkstra explored around 2,600 nodes compared to 7,200 for a standard single-direction search — close to a threefold improvement.

The second innovation is exploiting road hierarchy. Human intuition tells us that long journeys follow a predictable pattern: local roads → motorway → local roads. Algorithms have historically ignored this structure entirely, treating a narrow residential lane and an interstate highway as equivalent as long as their weights match.

Early in-car GPS systems tackled this by manually annotating roads into hierarchical categories — express highways, local major roads, narrow streets — and running bidirectional searches that progressively escalated through levels when the target wasn't found in the current tier. This reduced search areas dramatically, but came with a hard problem: how do you prove that a manually defined hierarchy never causes you to miss a true shortest path? A candidate area that's too small might return a highway route when a local road combination is actually faster. An area that's too generous starts approaching the inefficiency of plain Dijkstra.

Manual hierarchy annotation also doesn't scale well globally. What constitutes a "major road" in rural Montana is very different from one in central Tokyo, and human-assigned categories require constant updating as infrastructure changes.

The Pre-Processing Revolution: Contraction Hierarchies

The most powerful modern approach shifts significant computation away from query time and into a one-off pre-processing phase. The key insight is that you don't need to compute everything from scratch for every query — you can encode structural knowledge about the graph in advance.

Contraction Hierarchies (CH), developed by researchers at the Karlsruhe Institute of Technology and published in 2008, is the dominant technique behind modern high-performance routing. The algorithm iteratively "contracts" nodes — removing the least important intersections from the graph and replacing them with shortcut edges that preserve path distances. Importance is determined algorithmically: a node is less important if removing it doesn't force many new shortcuts to be added.

After contraction, what remains is a layered graph where higher-level nodes represent genuinely important junctions — major motorway interchanges, city gateways — and lower-level nodes represent local detail. A bidirectional query on this contracted graph only ever needs to travel upward through the hierarchy from both ends, meeting somewhere near the top. This constrains the search space to a tiny fraction of the full graph.

The pre-processing for the full European road network takes a few hours on modern hardware and produces a data structure that enables queries in microseconds — more than fast enough to serve millions of concurrent users. The trade-off is memory and preprocessing time, but for static or slowly changing road networks, this is entirely practical. Google, Apple, and HERE all use variants of this approach, often combined with additional techniques like Transit Node Routing and Customisable Route Planning that allow rapid updates when road conditions change.

What This Means Beyond Navigation

The progression from Dijkstra to Contraction Hierarchies isn't just a navigation story. It's a case study in how algorithmic thinking compounds. Each advance — A-star's heuristic, bidirectional search, hierarchical contraction — attacks a different structural property of the problem. None of them change the fundamental goal. All of them change what you choose to ignore.

This principle applies well beyond maps. Package routing networks, chip design, protein folding, logistics optimisation, and network traffic management all reduce to shortest-path problems at some level. The algorithms developed for navigation have found homes across industries precisely because the underlying graph structure is so universal.

Dijkstra himself never set out to solve navigation. He was trying to prove that computers were useful — at a time when Amsterdam's civil registry wouldn't even accept "programmer" as a legitimate profession. He designed his algorithm in 20 minutes, published it three years later in a journal that needed the content, and spent the rest of his career watching it become a cornerstone of computer science.

The next time your phone plots a route in four seconds across a continent of 64 million intersections, that's the lineage behind it: a cup of coffee, a simplified Dutch map, and one of the most elegant ideas in the history of computing — scaled up by six decades of refinement into something we now take completely for granted.

Frequently Asked Questions

What is Dijkstra's algorithm and why is it important?

Dijkstra's algorithm, developed by Edsger Dijkstra in 1956, finds the shortest path between two nodes in a weighted graph. It works by progressively exploring the lowest-cost unexplored node and guarantees an optimal solution. It's foundational to computer science and directly influenced every routing algorithm used in modern navigation systems.

Why doesn't Google Maps just use Dijkstra's algorithm?

On small city-level graphs, Dijkstra runs in under 100 milliseconds — perfectly fast. But on the full North American road network with 64 million intersections, Dijkstra takes around seven seconds per query on a single thread. Google Maps needs sub-millisecond performance to serve millions of simultaneous users, which requires pre-processing techniques like Contraction Hierarchies that compress the graph structure in advance.

What is A-star and how does it improve on Dijkstra?

A-star (A*) extends Dijkstra by adding a heuristic — typically straight-line distance to the target — to each node's priority score. This directs the search toward the destination rather than expanding in all directions, reducing the number of nodes explored by up to 10 times in distance-optimised routing. However, A-star underperforms for travel-time optimisation because the heuristic becomes a poor estimate when speed limits vary significantly across road types.

What are Contraction Hierarchies and how fast are they?

Contraction Hierarchies is a pre-processing technique that iteratively removes less important nodes from a road graph and replaces them with shortcut edges, creating a layered hierarchy. Bidirectional queries on this contracted graph only need to traverse upward through the hierarchy, drastically limiting the search space. After a preprocessing phase of a few hours, CH enables routing queries across continental road networks in microseconds — making it the backbone of production-grade navigation systems at companies like Google, Apple, and HERE.