Google Maps is Unreasonably Fast. Let Me Explain
Ask Google Maps for a route across a continent and the answer comes back almost instantly — yet the road network of North America contains far too many possibilities to check one by one. This Veritasium film explains the maths that makes that speed possible.
It starts with Dijkstra’s algorithm and the A* search, then moves to the tricks that make them fast at continental scale: road hierarchies that skip local streets until the final approach, and nested dissection for splitting huge maps into manageable pieces. With computer scientists including Aaron Bernstein, Tim Roughgarden and Jon Kleinberg, the film shows that the fastest route is not always the shortest one.
Key Themes & Topics Examined
- Shortest path algorithms and Dijkstra’s algorithm.
- The A* search algorithm in pathfinding.
- Why the fastest route is not always the shortest.
- Road network hierarchies for efficient route calculation.
- Nested dissection for handling large-scale map data.
- The speed and reliability of modern mapping applications.
Archival & Investigative Sources
- Interviews with Aaron Bernstein, Tim Roughgarden, Tomas Rokicki, Jon Kleinberg, Virginia Vassilevska Williams and Peter Sanders.
- Academic papers, including the SSSP Barrier Paper.
- Historical developments in route planning technology.
- Map data from OpenStreetMap contributors, licensed under the Open Database License.
Recommended Companion Viewing
Explore authoritative investigative documentaries on related historical events and investigative subjects.
How Flappy Bird Ruined The Life of its Creator
Before the Foldable, Apple Copied This Phone
An Unknown Engineer is Apple's New CEO
Dropbox Was Worth $10 Billion. Then Everyone Left
Frequently Asked Questions
What is a shortest path algorithm?
A shortest path algorithm is a method for finding a path between two nodes in a graph such that the sum of the weights of its constituent edges is minimized. In the context of mapping, this typically refers to finding the route with the least distance or travel time between two locations.
How does Google Maps determine the fastest route?
Google Maps employs a combination of advanced algorithms, including variations of Dijkstra’s and A* search, alongside real-time traffic data, historical traffic patterns, and road network hierarchies. It prioritizes factors like speed limits, road types, and current congestion to calculate the most time-efficient route, which may not always be the physically shortest path.
What is the significance of road network hierarchy in mapping applications?
Road network hierarchy involves categorizing roads based on their importance (e.g., highways, arterial roads, local streets). This hierarchical structure allows mapping applications to efficiently prune search spaces, focusing on higher-level roads for long-distance travel and only delving into lower-level roads when nearing the destination, significantly reducing computational load and improving search speed.

