Live model · Google Maps routing
How Google Maps Routing Actually Works
A navigation app treats roads as a graph: intersections joined by road segments, each weighted by its predicted travel time. The classic search, Dijkstra's algorithm, grows outward from you, always extending the quickest route found so far. A* adds a straight-line guess of the time left, so it wastes less work. Traffic changes the weights, and with them the route.
Dijkstra, one intersection at a time
- CH1 In the queue
- CH2 Highway, 100 km/h
How to read the stage
Each pill is an intersection, and its badge is the best time found so far. The queue holds places reached but not yet settled, smallest time first. Each step settles the top one, since nothing can reach it faster, and tries its roads. Dijkstra settles 20 of the 22 intersections before the Airport comes off the queue at 11:28, including Pine, Mill, Oak and Elm, which lie behind Home.
Aim at the destination
A* keys the queue by time so far plus the time left in a straight line at 100 km/h, the top speed on this map. No road is straighter or faster, so the guess never overestimates, and Hart, Nilsson and Raphael proved in 1968 that A* then still returns the best route. Here it settles 11 intersections instead of 20 and finds the same 11:28 down the highway.
A*: the same search, aimed at the Airport
- CH1 In the queue
- CH2 Highway, 100 km/h
Traffic changes the weights
Jam the middle of the highway and its 2:19 becomes 11:35. The search runs exactly as before on the new numbers. Down the highway now takes 20:44, so the route goes through downtown instead: Main, Plaza, the bridge and the Mall, in 12:34. Google Maps predicts each road's time from its traffic history combined with live conditions, using machine learning.
A jam on the highway
- CH1 In the queue
- CH2 Highway, 100 km/h
What Google adds
A continent has tens of millions of intersections, far too many to settle on every request. Fast planners precompute shortcuts once. Contraction hierarchies, published in 2008, answered queries on Western Europe's 18-million-intersection network in about 0.2 milliseconds. Google doesn't publish its router. It has published its traffic forecasts: graph neural networks built with DeepMind improved arrival-time accuracy by up to 50% in cities such as Berlin, Sydney and Tokyo.
What the model leaves out
Real maps have one-way streets, turn costs, traffic lights, tolls and ferries, and travel times that change through the day. Here every road has one fixed time and runs both ways, and a jam simply multiplies one road's time by five. The model's A* guess is a straight line at top speed; real planners use precomputed bounds that are much tighter, so they waste far less work.
Questions
- Does Google Maps use Dijkstra's algorithm?
- Google hasn't published its routing algorithm. Dijkstra's algorithm and A* are the classics the fast methods build on: techniques such as contraction hierarchies precompute shortcut roads once, then run a Dijkstra-style search over them, so each request settles a tiny fraction of the map.
- How does Google Maps calculate arrival time?
- It predicts each road's travel time for the moment you'll reach it, from historical traffic patterns for that road combined with live conditions, using machine learning, and adds them up along the route. Google says its predictions have been consistently accurate for over 97% of trips.
- How does Google Maps know about traffic?
- When people navigate with Google Maps, aggregate location data shows how fast traffic moves on each road. Google combines that live picture with each road's history, and in 2020, after the pandemic upended traffic, it began favoring patterns from the last two to four weeks.
- Why did Google Maps change my route?
- Because the predicted times changed. A route is the smallest sum of road times, and when a slowdown raises one road's time enough, another sum becomes smaller. On the stage, the highway jam moves the route downtown: 12:34 against 20:44. A small slowdown on a clearly faster route changes nothing; try jamming the bridge.
- Is A* always faster than Dijkstra?
- It saves work when its guess of the time left is close to the truth. A straight line at 100 km/h is a weak guess where most roads are slower. Send the stage to the Hotel, reached only by 40 km/h streets, and A* settles all 22 intersections, as many as Dijkstra.
Drill the mechanism
Route search is a graph traversal with a priority queue in place of a plain one: a visited set, a frontier, and a heap that always hands back the smallest key. Number of Islands drills the traversal and its visited set. Kth Largest Element and Meeting Rooms II drill the heap.