Math Tools Math Tools
Share:
← Back to Blog

The Math Behind Google Maps

The Math Behind Google Maps

By Math Tools ·

The Math Behind Google Maps

The algorithm at the heart of most route planners was designed in about 20 minutes. In 1956, Dutch computer scientist Edsger W. Dijkstra was shopping in Amsterdam with his fiancée. Tired, they sat down on a café terrace, and he worked out how to find the shortest route between two cities, without pencil or paper.

Nearly 70 years later, versions of that idea help plan routes for over a billion people. But running it naively on a map of the whole world would be far too slow. The story of Google Maps is the story of making an old algorithm fast, and then predicting the future.

The Shortest Route on a Map Isn't a Straight Line

On a flat map, the shortest path between two points looks like a straight line. On a sphere, it isn't. The shortest route between two points on Earth follows a great circle, and on the flat Mercator projection most web maps use, great circles look curved.

That's why flights from New York to Tokyo arc up toward Alaska. On the globe, that "detour" is the straight path.

Step 1: The Map Is a Graph

To a routing engine, a road network is a graph:

  • Nodes (vertices) are intersections
  • Edges are road segments between them
  • Weights are travel times (or distances) on each edge

Graph theory began in 1736, when Leonhard Euler proved it was impossible to walk through the city of Königsberg crossing each of its seven bridges exactly once. He realized that only the connections mattered, not the exact geography, and that insight is what lets a routing engine throw away everything except nodes, edges and weights.

Step 2: Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from a starting node to every other node:

1. Set distance(start) = 0 and every other distance = ∞
2. Pick the unvisited node with the smallest known distance
3. For each neighbor, if distance(current) + edge weight
   is less than distance(neighbor), update it
4. Mark the current node visited and repeat from step 2

It's a greedy algorithm: it always extends the closest unexplored frontier, and it's guaranteed to be correct as long as no edge weight is negative. With a priority queue, it runs in about O((V + E) log V) time, where V is the number of nodes and E is the number of edges.

The problem is scale. Dijkstra's algorithm grows outward in all directions like a ripple, so a cross-country route would explore millions of irrelevant roads.

Step 3: A* Search Aims Toward the Goal

In 1968, Peter Hart, Nils Nilsson and Bertram Raphael at the Stanford Research Institute published A* (A-star). It adds a heuristic, an estimate of the remaining distance to the destination:

priority(node) = distance so far + estimated distance to goal

For road maps, a good heuristic is the straight-line distance to the destination divided by the highest possible speed. Because that never overestimates the true travel time, A* is still guaranteed to find the optimal route, but it explores far fewer nodes by leaning toward the goal.

Step 4: Preprocessing With Contraction Hierarchies

Even A* is too slow for continent-sized maps with millisecond response times. Modern routing engines precompute shortcuts. One well-known technique is contraction hierarchies, introduced by Robert Geisberger and colleagues at Karlsruhe Institute of Technology in 2008.

The idea: rank nodes by importance (a quiet cul-de-sac is low, a highway interchange is high). Remove unimportant nodes one by one, adding shortcut edges that preserve shortest-path distances. At query time, the search only climbs "up" the hierarchy from both ends and meets in the middle. Queries that took seconds now take microseconds.

Step 5: Distance on a Sphere

To measure the straight-line distance between two GPS coordinates, map software uses the haversine formula:

a = sin²(Δφ/2) + cos φ₁ · cos φ₂ · sin²(Δλ/2)
d = 2R · arcsin(√a)

Where φ is latitude, λ is longitude (both in radians) and R ≈ 6,371 km is Earth's mean radius.

From New York (40.7128° N, 74.0060° W) to London (51.5074° N, 0.1278° W), this gives about 5,570 km. Try the pieces yourself: convert with degrees to radians, then use the sine and arc sine calculators.

Step 6: Predicting Traffic

The shortest route right now isn't what you need. You need the fastest route over the next 40 minutes. That means forecasting traffic.

Google combines historical speed patterns for each road segment at each time of day with live, anonymized location data. In 2020, Google and DeepMind described using graph neural networks, which learn directly on the road graph, to predict travel times. They reported improving the accuracy of real-time arrival estimates by up to 50% in cities such as Berlin, Jakarta, São Paulo, Sydney, Tokyo and Washington, D.C.

Two Concepts Worth Knowing

Map Projections

No flat map can preserve both angles and areas of a sphere, a result that follows from Gauss's Theorema Egregium (1827). Web maps use Web Mercator, which preserves local angles (so streets meet at the right angles) but badly distorts area near the poles. That's why Greenland looks about as big as Africa, which is actually around 14 times larger.

Big-O Notation

Big-O notation describes how an algorithm's running time grows with input size. It's the language engineers use to compare Dijkstra, A* and contraction hierarchies, and to explain why preprocessing pays off for billions of queries.

Quick Answer: What Algorithm Does Google Maps Use?

Google Maps models roads as a weighted graph and finds routes with shortest-path algorithms descended from Dijkstra's algorithm and A* search, sped up with precomputed shortcuts. Travel-time weights come from historical and live traffic data, predicted with machine learning models such as graph neural networks.

Try Them Yourself

Pick two cities, look up their coordinates, and compute the great-circle distance with the haversine formula. Then compare it with the driving distance your map app shows.

Next → The Math Behind Google Search