Key Moments
How Does Google Maps Actually Work?
VeritasiumWant to know something specific about what's covered?
We've already dissected every moment. Ask and we will deliver (with timestamps).
Key Moments
Google Maps achieves near-instant routing by using a highly optimized 'customizable contraction hierarchy' which pre-processes road networks to drastically reduce search time, making a 7-second Dystra algorithm 35,000 times faster.
Key Insights
The brute-force calculation of all possible routes has an estimated 10^220 possibilities, making it computationally impossible within human timelines.
Dijkstra's algorithm, developed in 1956, finds the shortest path by exploring nodes in increasing order of distance from the source, guaranteeing the optimal route.
On large networks like North America, a well-tuned Dijkstra's algorithm can take around 7 seconds per path, exploring most of the 64 million nodes, which is too slow for simultaneous user requests.
A* search, a modification of Dijkstra's, uses a heuristic (like straight-line distance to the target) to prioritize nodes, significantly reducing the search space by up to 10 times.
Customizable Contraction Hierarchies (CCH) reduce query times to hundreds of microseconds by pre-processing road networks to create a hierarchy of node importance, allowing bidirectional searches that meet in the middle.
The pre-processing phase for CCH, including ordering nodes and adding shortcuts, can take around 1 hour 40 minutes on the North American network, while updates for traffic can be done in seconds.
The impossible scale of finding the shortest path
Calculating the absolute shortest path between two points in a vast road network, like North America's 64 million intersections, presents an astronomical computational challenge. A simplified estimate suggests over 10^220 possible routes. Even with modern computers checking a billion routes per second, exhaustively testing every path would take over 10^200 years. This problem isn't unique to navigation; robots and video game characters face similar challenges in complex environments. Yet, applications like Google Maps provide routes in mere seconds, highlighting the need for highly efficient algorithms beyond brute-force methods.
Dijkstra's foundational algorithm for shortest paths
The origins of efficient pathfinding trace back to Edsger W. Dijkstra in 1956. While working on early computers at the Mathematical Centre in the Netherlands, Dijkstra sought a practical demonstration of computing power. He devised a shortest path algorithm to find the quickest route between two cities. Initially, a simple 'breadth-first search' could work if all roads were equal in length, by exploring neighbors layer by layer. However, real-world roads have varying distances. Dijkstra's breakthrough was an algorithm that keeps track of the shortest distance found so far to each node from the source. It starts with the source node at distance zero and all others at infinity. In each step, it explores the unvisited node with the smallest known distance, updates the distances of its neighbors, and marks the current node as visited. This greedy approach guarantees finding the shortest path because it systematically explores paths in increasing order of length. Dijkstra famously conceived this elegant 20-minute invention without a pen or paper, emphasizing simplicity and avoiding unnecessary complexity.
Limitations of Dijkstra's for real-world mapping
While Dijkstra's algorithm is elegant and foundational, it struggles with the scale and speed required by modern mapping services. For instance, finding a route from Newark airport to the Central Park Zoo, a relatively short journey, might involve Dijkstra exploring over 65,000 nodes. Even these explorations can take about a tenth of a second, which seems fast. However, when comparing average query speeds across a large network like North America, Dijkstra's algorithm takes around 7 seconds per path, often exploring most of the 64 million nodes. The critical issue is that millions of users might request directions simultaneously. To meet the sub-second response times needed by Google Maps, algorithms must be thousands of times faster. Dijkstra's undirected search explores in all directions, including many illogical ones, making it too slow for widespread, high-volume use.
A* search: Guiding the search with heuristics
To overcome Dijkstra's inefficiency, the A* search algorithm introduces a heuristic – an educated guess – to guide the search. Instead of just considering the cost from the source to the current node, A* also factors in the estimated cost from the current node to the target. By prioritizing nodes that are both close to the source and likely to be on the path to the target (e.g., using straight-line distance), A* significantly prunes the search space. Visualized as stretching the graph into 3D space where height represents distance to the target, A* effectively penalizes moves going 'uphill' away from the destination. This modified Dijkstra can reduce the number of explored nodes by approximately 10 times compared to plain Dijkstra. A* is widely used in video games for non-player characters (NPCs) and maze-solving because it can dramatically speed up pathfinding, though its worst-case performance can still match Dijkstra's.
Bidirectional search: Meeting in the middle
Another optimization is bidirectional search, which runs Dijkstra's algorithm simultaneously from both the source and the target. Imagine two search frontiers expanding towards each other. When these frontiers meet, the shortest path can be determined. This overlap significantly reduces the total area searched. For a path of distance 'r', a single search might explore nodes within a circle of area πr². Bidirectional search, however, can reduce this area to roughly half that of a single search by having the frontiers meet at approximately r/2. On a New York City graph, this approach showed a nearly threefold improvement, reducing the number of explored nodes from over 7,200 to just over 2,600. However, this method still doesn't fully leverage the inherent structure of road networks.
Customizable Contraction Hierarchies: Exploiting road network hierarchy
Modern routing algorithms like Google Maps likely employ sophisticated techniques such as Customizable Contraction Hierarchies (CCH). CCH builds upon the idea of road hierarchy, recognizing that people intuitively use local roads to reach main roads, then highways, and then local roads again near their destination. The algorithm preprocesses the road network by assigning importance ranks to nodes. Nodes that are critical for long-distance travel, like bridges over major rivers (e.g., the Mississippi) or junctions connecting major highways, receive higher ranks. This ranking process, often using a 'nested dissection' method, identifies 'cuts' that divide the graph into smaller, manageable parts. The preprocessing involves ordering nodes by importance and adding 'shortcuts' – precomputed paths between higher-ranked nodes. This allows for a highly optimized bidirectional search where the two search frontiers meet at the top of the hierarchy. The entire CCH process is divided into phases: phase one is the expensive but infrequent node ordering and shortcut creation (taking about 1 hour 40 minutes for North America), phase two is calculating shortcut weights (seconds, updatable for traffic), and phase three is the actual search. This results in query times of mere hundreds of microseconds, an improvement of tens of thousands of times over Dijkstra, exploring significantly fewer nodes (around 1,450 for a long trip on the North American network).
The enduring legacy of simplicity and reliability
Despite the complexity of mapping algorithms, they are fundamentally built upon foundational concepts, many of which trace back to Dijkstra's 70-year-old algorithm. The efficiency gains in modern systems like Google Maps, achieved through techniques like contraction hierarchies, are essentially optimizations and extensions of Dijkstra's core idea. Dijkstra himself emphasized simplicity as a prerequisite for reliability, believing that programmers should be accountable for their work. His hope was that his algorithm would serve as a guiding principle for programmers to create elegant and thoughtful solutions, a sentiment that clearly underpins the development of the systems we use daily.
Mentioned in This Episode
●Software & Apps
●Companies
●Concepts
●People Referenced
Algorithm Performance Comparison
Data extracted from this episode
| Algorithm | Average Query Speed (North America Network) | Nodes Explored (Average for Long Path) | Speed Improvement over Dijkstra |
|---|---|---|---|
| Dijkstra's Algorithm | ~7 seconds per path | ~64 million nodes | N/A |
| Dijkstra's Algorithm (Bidirectional) | N/A (improves overlap) | ~2,600 nodes (Carnegie Hall to Wall Street example) | ~3x improvement in nodes explored |
| A* Search (with heuristic) | N/A (can vary) | Varies, up to 10x improvement over Dijkstra in some cases | Can be significant, especially for single-destination searches |
| Customizable Contraction Hierarchy | ~200 microseconds (average) | ~1,450 nodes | ~35,000x faster (or ~44,000x reduction in search space) |
Common Questions
Google Maps uses advanced algorithms that go beyond simple brute-force calculations. While there are an astronomical number of possible routes, techniques like Dijkstra's algorithm, A* search, and more complex methods like contraction hierarchies pre-process the road network to drastically reduce the search space, allowing for near-instantaneous route calculation.
Topics
Mentioned in this video
Navigation software that finds routes quickly, leveraging advanced algorithms. The video explains the complexity of its routing calculations.
A graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge weights. It was developed without pencil and paper by Edsger Dijkstra.
A programming language discussed as a bottleneck for certain jobs, particularly in data science, with a high percentage of job listings requiring knowledge of it.
A programming language, mentioned as being required for a high percentage of data science jobs, and also used in scripts to experiment with pathfinding algorithms.
A navigation application mentioned alongside Google Maps as an example of services that efficiently find routes.
A collaborative project to create a free, editable map of the world, providing actual maps used to experiment with pathfinding algorithms.
An advanced algorithm that combines pre-processing, graph hierarchy, and bidirectional search to achieve extremely fast routing query times, outperforming Dijkstra's algorithm significantly.
Mentioned as a starting point for calculating the shortest driving path to San Francisco.
Mentioned as a destination for calculating the shortest driving path from New York.
The city where Dijkstra was working and conceived of his famous shortest path algorithm during a shopping trip.
The country where Dijkstra worked and developed his algorithm, using a simplified map of its cities and roads for his demonstrations.
A city in the Netherlands used as an example starting point for Dijkstra's shortest path problem.
A city in the Netherlands used as an example destination for Dijkstra's shortest path problem.
An airport in New Jersey used as an example location for demonstrating Dijkstra's algorithm's limitations and the need for faster methods.
A destination in New York City used as an example for pathfinding algorithms, illustrating search space expansion.
A borough of New York City, mentioned as an example of a location explored by Dijkstra's algorithm that is far from the target.
A concert venue in New York City used as an example for comparing bidirectional Dijkstra's search efficiency against a single direction search.
A street in New York City's financial district, used as an example destination for bidirectional Dijkstra's search.
A major river in North America, mentioned as a significant geographical feature that acts as a bottleneck and is considered in contraction hierarchy algorithms.
A river in the eastern United States, identified as part of a significant cut in the North American road network during the nested dissection process.
A mountain range in eastern North America, mentioned as part of a significant cut in the North American road network during the nested dissection process.
A mountain range in western North America, identified as part of a significant cut in the North American road network during the nested dissection process.
A river in the western United States, identified as part of a significant cut in the North American road network during the nested dissection process.
A city in Canada, used as a destination in an example comparing Dijkstra's search space with that of a customizable contraction hierarchy.
An algorithm for traversing or searching tree or graph data structures, which explores all nodes at the present depth prior to moving on to nodes at any greater depth. It was the initial approach before Dijkstra's improvements.
A graph partitioning technique used in the pre-processing phase of contraction hierarchies to recursively divide the graph and identify important bottleneck nodes.
Sponsor of the video, offering coding courses that teach fundamentals through problem-solving, including running Dijkstra's algorithm and covering languages like SQL, Go, Docker, Linux, and AWS.
A fast-food chain mentioned in the context of suboptimal pathfinding, where algorithms might consider illogical routes like driving into a drive-thru.
More from Veritasium
View all 97 summaries
22 minCan a quantum sensor detect your heartbeat from 60 km away?
34 minThe disaster I never imagined having to worry about
27 minCan you steal $10,000 from a locked iPhone?
59 minWhy Is CERN Making Antimatter?
Ask anything from this episode.
Save it, chat with it, and connect it to Claude or ChatGPT. Get cited answers from the actual content — and build your own knowledge base of every podcast and video you care about.
Get Started Free