How Google Maps Finds Your Route
Every road on Earth is one edge in a graph, weighted not in miles but in seconds. Plain Dijkstra would search nine million junctions and take two seconds; the trick Google actually uses pre-builds a hierarchy of shortcuts over the map, so the query only ever climbs upward — and touches a few hundred junctions in a tenth of a millisecond.
Step 01 of 09
1 · The line you already trust
Two taps, and a blue ribbon appears through a city you have never driven. It arrived in about a tenth of a second, and it is not the shortest route — it is the fastest one. Everything under this map exists to answer one question: out of the millions of ways from this pin to that one, which gets you there soonest?
Step 02 of 09
2 · The weight is time, not distance
Every edge carries a number, and it is not its length — it is how long it takes: length divided by the speed that road actually moves at. The expressway here runs about three times the speed of the side street beside it, so two kilometres of motorway can cost less than four hundred metres of stop-start. Choosing seconds instead of metres is the entire reason the app sends you the long way round and still wins.
Step 03 of 09
3 · Strip the map away
The buildings are decoration. What the router sees is this: every junction a node, every stretch of road between two junctions an edge, stored twice over because a street can be quicker one way than the other. This district has 81 junctions and 160 segments. Western Europe — the benchmark this field measures itself against — has 18 million junctions and 42.5 million.
Step 04 of 09
4 · Dijkstra: cheapest first, in every direction
The classic answer, published by Edsger Dijkstra in 1959: always expand from the cheapest junction you have reached but not yet finished with. Do that and the search grows as a circle of equal travel time — outward in every direction, including straight away from where you are going. Here it settles 71 of the 81 junctions to find one route. On Western Europe it settles 9,326,696 of them, and takes about two seconds.
Step 05 of 09
5 · A*: aim the search at the destination
Add one number to every junction — an estimate of the time still to go, straight-line distance divided by the fastest speed anywhere on the network. Because that estimate can never come out too high, the answer stays exactly correct, but the search now prefers junctions that face the destination and the circle stretches into a teardrop. 43 junctions here instead of 71.
Step 06 of 09
6 · Search from both ends at once
Run a second search backwards from the destination and advance whichever front is currently cheaper. Two half-sized searches cost far less than one full-sized one, and both can stop the moment their cheapest remaining pair can no longer beat the best meeting point already found. 33 junctions here, meeting in the middle. On Western Europe this halves the work to 4.9 million — and still takes more than a second.
Step 07 of 09
7 · Build the shortcuts before anyone asks
Everything so far searches the live map. The technique that makes continent-scale routing practical does the expensive part once, offline: rank every junction by importance, then delete them one at a time from the least important upward. Whenever deleting one would break the only shortest path between two of its neighbours, drop in a shortcut edge carrying exactly that travel time. 25 shortcuts cover this district; the whole of Western Europe takes about five minutes.
Step 08 of 09
8 · The query is only allowed to climb
With the shortcuts in place, each of the two searches is forbidden from ever moving downward in the hierarchy. From your side street it climbs to the arterial, to the expressway, and stops. The two upward searches meet near the top, and unpacking the shortcuts they used hands back exactly the route Dijkstra found the slow way. 24 junctions here. On Western Europe: 280 junctions, 110 microseconds — roughly twenty thousand times faster than where we started.
Step 09 of 09
9 · The weights move while you drive
The map comes back, and with it the part no preprocessing can bake in: every phone running the app reports how fast it is moving, and those anonymised traces — blended with years of history for this road at this hour — become the live weight on each edge. When the corridor ahead jams, the numbers change and the route is simply solved again against the new ones. Google puts its arrival times within a few minutes on more than 97% of trips.