Most people use maps every day. Very few know what actually happens when they tap “Go”.
When a route appears on Google Maps, Mapbox, or any navigation app, it looks trivial: two points, one line, an ETA. In reality, that result comes from years of research in graph theory, geospatial indexing, and algorithmic optimization.
The real problem is not drawing a line on a map. The real problem is finding an optimal path on a real-world road network, under constraints.
Step 1: Two GPS Coordinates
Everything starts with:
Origin: (lat, lon)
Destination: (lat, lon)These are raw floating-point numbers. The road network doesn’t understand coordinates — it understands nodes and edges.
Step 2: Map Matching — Snapping to the Graph
The first real challenge: your GPS position is not on a road. It’s a point in space. The engine must snap it to the nearest valid road segment.
This uses spatial indexing — typically an R-tree or similar structure — to find the nearest road geometry efficiently without scanning every road in the dataset.
Step 3: The Road Network as a Graph
Every city’s road network is modeled as a directed weighted graph:
- Nodes = intersections, road endpoints
- Edges = road segments connecting them
- Weights = travel time (not just distance)
Weights are dynamic. A 2km road at 100 km/h has a very different weight than the same road in rush hour at 15 km/h.
Step 4: Shortest Path — But Not Dijkstra
Naïve Dijkstra on a graph of millions of nodes is too slow for real-time queries.
Modern routing engines use variants and preprocessing techniques:
- Contraction Hierarchies (CH) — pre-contract unimportant nodes during preprocessing; queries run on a much smaller graph
- A* — Dijkstra with a heuristic (straight-line distance to destination) to explore fewer nodes
- Customizable Route Planning (CRP) — used by Bing Maps; separates metric customization from graph structure
Google and Apple run proprietary variants, but the core ideas come from these algorithms. A query that would take seconds on raw Dijkstra runs in milliseconds on a properly preprocessed graph.
Step 5: Real-World Constraints
The graph isn’t static. The engine must handle:
- Turn restrictions — no U-turns, no left turns at certain intersections
- One-way streets — directed edges
- Road access rules — motorway vs. residential, vehicle type restrictions
- Live traffic — edge weights update in real time from probe data (GPS signals from other phones)
- Time-dependent weights — school zones, rush hour patterns
Step 6: The ETA
Distance is easy. Time is the hard part.
ETA comes from historical traffic models (what does this road look like at 8am on a Tuesday?) combined with real-time probe data (what are people actually experiencing right now?).
The result is a weighted combination — probabilistic, not deterministic.
What’s Running Under Google Maps
Google doesn’t publish its full stack, but the general architecture is:
- Preprocessing — road graph contracted and indexed offline (updated continuously)
- Spatial index — for map matching and nearby searches
- Routing engine — custom CH/A* variant running in distributed compute
- Traffic layer — real-time aggregation from billions of GPS pings
- ETA model — ML model over historical + live traffic features
The “line on the map” is the visible output of a system that processes petabytes of data to answer your query in under 200ms.