Dijkstra to Google Maps: How Shortest Path Algorithms Power Real-World Routing

Summary

Veritasium walks through the fundamental challenge of routing from one city to another, showing why brute‑force checking every possible route is computationally infeasible even with massive processing power. The video traces the birth of shortest-path algorithms, starting with breadth‑first search and evolving to Dijkstra’s weighted graph algorithm, highlighting how costs (distances) change the problem dramatically. It then introduces smarter strategies such as heuristics with A*, bidirectional search, and road hierarchies to dramatically cut the search space. The talk also explains how modern systems like Google Maps rely on automated pre processing to build a hierarchy of nodes and shortcuts, yielding near real‑time routing on enormous road networks.

• Key insights into why naive search fails on large graphs
• Introduction to Dijkstra, A*, and bidirectional search
• Hierarchical pre processing and contraction hierarchies unlock milliseconds‑level routing
• Real‑world implications for maps, games, and robotics

Overview

This video provides a narrative journey from the basic shortest path problem to the sophisticated routing techniques used by modern maps. The speaker frames a practical scenario: driving from Newark to Central Park Zoo, and uses this example to illustrate how a naive search would need to explore tens of thousands of nodes, making instant routing unrealistic for millions of simultaneous queries. The discussion then builds from simple ideas to more advanced algorithms, revealing how the core ideas from Dijkstra still underpin today’s fastest routing systems.

From BFS to Dijkstra

The earliest approach to finding the shortest path in a graph is a breadth first search (BFS) that treats every road as equal length. In a weighted graph, this equality breaks down because some edges are longer than others. This motivates the introduction of a cost for each node, representing the shortest known distance from the source to that node. The algorithm proceeds by repeatedly selecting the unexplored node with the smallest cost and relaxing its edges to potentially lower neighboring costs. Over time, the costs converge to the true shortest distances from the source to every reachable node, and the path to the destination can be reconstructed. Dijkstra’s algorithm formalizes this relaxation process, guaranteeing the shortest path is found when edges have non negative weights.

Limitations on Large Graphs

While Dijkstra’s algorithm is elegant, it becomes impractical on networks with millions of nodes. A typical city graph may be fast, but a continental network with tens of millions of intersections is a different scale. A standard Dijkstra search could still be fast for one query, but the volume of queries for a service like Google Maps requires many orders of magnitude faster performance. The video demonstrates that even with modern hardware, the time required for Dijkstra to complete a single long route would be far too long if every query executed in isolation.

Heuristics and A*

To accelerate pathfinding, a heuristic that estimates the remaining distance to the target is used. A* combines the actual cost from the source with a heuristic estimate to guide the search toward the target. The straight line distance to the target is a natural and informative heuristic for road networks. By steering the search toward the zoo, for example, A* reduces the number of explored nodes dramatically, often by an order of magnitude or more. The speaker also notes that for different optimization goals, such as travel time rather than geographic distance, different heuristics can influence search behavior and efficiency.

Bidirectional Search

Another improvement is bidirectional search, which runs two simultaneous searches: one from the source and one from the target. The two frontiers meet in the middle, reducing the explored area substantially. In practice, this can shrink the node exploration by roughly a factor of three in examples like going from Carnegie Hall to Wall Street. The talk emphasizes that bidirectional search alone does not exploit the road network's hierarchy, so additional techniques are still needed for best performance on large graphs.

Hierarchies and Pre processing

The key insight for real‑world routing is that road networks have a hierarchy: local streets connect to arterial roads, which connect to highways. Early GPS systems used manually crafted road classes and layered searches to first explore local roads, then limitedly escalate to higher‑level roads. The challenge is to create a hierarchy that preserves the shortest path and is robust to changes like closures. The video introduces the idea of nested dissection, which partitions the graph into halves and ranks nodes by their importance in cutting across the graph. These ranks then guide the search to explore fewer nodes, while still guaranteeing optimal paths through a process of introducing shortcuts that connect higher‑level nodes directly.

Contraction Hierarchies and Shortcuts

Contraction hierarchies are a form of pre processing that orders nodes and adds shortcuts to ensure the shortest path remains discoverable even when the search only traverses high‑rank nodes. Shortcuts encode the effect of potentially many lower‑rank paths, enabling the query to skip large portions of the original graph. The construction phase adds these shortcuts bottom up, ensuring that any path that uses lower rank nodes can still be reconstructed efficiently using the shortcuts. The approach also considers potential variants where the ranking only approximately halves the graph and relies on shortcuts to fill in any missing shortest paths.

Phases of the Customizable Contraction Hierarchy

Phase one builds a node ordering and adds shortcuts. This phase is the most expensive but once completed, the structure remains valid even as minor changes occur. Phase two computes the weights of the shortcuts so that actual route lengths remain correct when edge weights update with changing traffic. Phase three performs the actual search, typically using bidirectional searches across the hierarchy. In North America, this approach yields turnaround times measured in microseconds and node exploration counts that are orders of magnitude smaller than plain Dijkstra. The result is query speeds well below a millisecond, enabling reliable routing under heavy load.

Impact and Real World Implications

The video emphasizes that Google Maps and similar services likely use a contraction hierarchy style technique or a closely related method. While the exact internals are not disclosed, the general principle is to combine smart preprocessing with efficient forward and backward search, leveraging the road network’s inherent hierarchy. The talk concludes by reflecting on Dijkstra’s enduring influence, noting that modern routing algorithms are built on top of his simple and reliable idea, often enhanced with hierarchy, heuristics, and bidirectional search. In addition to maps, these concepts also apply to robotics, video games, and other pathfinding tasks where fast, reliable navigation is essential.

Takeaways

The core takeaway is that the shortest path problem is computationally tractable at scale only when you combine a solid mathematical foundation with intelligent preprocessing and search strategies that align with real world structures. Dijkstra’s algorithm remains a foundational building block, but practical systems rely on layered methods to deliver fast, reliable results across enormous graphs.