The Algorithm That Powers Google Maps

Imagine trying to find the absolute shortest driving route from New York to San Francisco. With over 64 million intersections in North America, the number of possible routes is astronomical – around 10 to the power of 220. Even if you could check a billion routes per second, it would take over 10 to the power of 200 years to test them all. This isn't just a problem for navigation; any system requiring navigation, like a robot or a video game character, faces the same challenge. Yet, services like Google Maps can find you a route in mere seconds. How is this possible?

The answer lies in the power of shortest path algorithms, a concept that traces its origins back to a shopping trip in Amsterdam in 1956.

The Birth of a 20-Minute Invention

Edsger Dijkstra, a computer scientist working on ARMAC, an early computer at the Mathematical Center in the Netherlands, needed a compelling demonstration of its capabilities. At the time, computers were widely considered useless, so much so that Dijkstra himself was humorously listed as a "theoretical physicist" on his marriage license because "programmer" wasn't recognized as a profession. He needed a problem that non-mathematicians could understand and appreciate the solution to.

During a shopping trip with his fiancée, Dijkstra conceived of the perfect problem: "What's the shortest way to travel from Rotterdam to Groningen?" This question led to the development of the shortest path algorithm.

Breadth-First Search: The Simple Approach

A simplified way to visualize this is with a graph, where cities are nodes and roads are edges. The most basic approach, known as Breadth-First Search (BFS), explores all neighboring nodes from the starting point. It systematically checks all nodes one step away, then two steps away, and so on. This guarantees finding the shortest path in terms of the number of steps.

However, BFS treats all roads as equal. In reality, roads have different lengths. To account for this, we assign weights to the edges, representing distances. This is where BFS becomes insufficient, and Dijkstra needed a more sophisticated method.

Dijkstra's Algorithm: Finding the Shortest Weighted Path

Dijkstra's breakthrough came during another moment of reflection, this time over coffee on a cafe terrace. His idea was to keep track of the shortest known distance (or "cost") from the source node to every other node in the graph.

The algorithm starts with the source node having a cost of zero and all other nodes having an infinite cost. Then, it iteratively explores the node with the lowest current cost among the unexplored nodes. For each explored node, it examines its neighbors and updates their costs if a shorter path is found through the current node.

For example, if the current node has a cost of 3 and an edge to a neighbor has a weight of 2, the neighbor's cost is updated to 5. If later, another path to that same neighbor is found with a cost of 4, its cost is updated again to 4. This process continues, always selecting the unexplored node with the lowest cost, until the destination is reached.

Dijkstra's algorithm guarantees finding the shortest path because, at each step, it has already explored all possible paths with costs lower than the current lowest-cost unexplored node. If the lowest cost among unexplored nodes is 18, it means all paths with costs less than 18 have already been considered, and if none reached the destination, then the current lowest-cost path to the destination must be the shortest.

Dijkstra famously described his algorithm as a "20-minute invention" that he designed "without pencil and paper," which he believed forced him to avoid unnecessary complexities.

The First Route Planner

When ARMAC was officially inaugurated in 1956, Dijkstra demonstrated his algorithm by having audience members choose two towns on a map. ARMAC then printed the shortest route, and the demonstration was a resounding success. While the algorithm sat in his papers for years, it was eventually published in 1959 and became a cornerstone of his fame.

Despite its elegance, Dijkstra's algorithm isn't always sufficient for modern applications like Google Maps. Consider navigating from Newark Airport to the Central Park Zoo. Dijkstra's algorithm would explore outwards in all directions, checking all possible 10km journeys, then 20km, and so on. This search frontier can become enormous, encompassing areas far from the target, like Staten Island and large parts of New Jersey. While it might find the route quickly (around a tenth of a second on a phone), the sheer number of nodes explored can be inefficient for massive networks.

A* Search: Adding Heuristics for Smarter Navigation

The problem with Dijkstra's algorithm is that it explores in all directions, even those moving away from the target. To improve efficiency, we can introduce a heuristic – an educated guess – to guide the search.

The A* (A-star) search algorithm modifies Dijkstra's by prioritizing nodes that are not only close to the source but also appear to be closer to the target. This is achieved by adding the straight-line distance (calculated using longitude and latitude) from a node to the target as part of its cost. The algorithm then orders nodes by their total cost (path from source + estimated distance to target).

This "penalizes" moves that take the search further away from the destination, making the search frontier head more directly towards the target. A* can significantly reduce the number of nodes explored, often by an order of magnitude. This makes it highly effective for applications like video game NPCs, where efficient pathfinding is crucial.

However, optimizing for the shortest geographic distance isn't always the same as optimizing for the fastest travel time. When considering travel time, A* can sometimes be outperformed by a well-tuned Dijkstra because the heuristic calculations themselves can add overhead.

Bi-directional Search and Road Network Hierarchy

To further optimize, map applications employ other strategies. One is bi-directional search, where the search is run simultaneously from both the source and the target. The two search frontiers meet in the middle, significantly reducing the overall search area.

Another crucial insight is the hierarchy of road networks. Humans intuitively understand that we tend to use local roads to get to a highway, then use the highway for long distances, and finally exit the highway to use local roads again near our destination. Traditional algorithms like Dijkstra and A* don't inherently understand this hierarchy, treating a local road and a highway with the same weight as equally viable options.

Customizable Contraction Hierarchies

To address this, modern routing algorithms leverage pre-processed hierarchies. This involves automatically ordering nodes by their importance. For example, an intersection connecting two highways is far more important than one leading to a cul-de-sac.

This pre-processing step, known as nested dissection, identifies "bottleneck" nodes that are critical for connecting different parts of the graph. For instance, bridges over a major river or key intersections that split the graph into roughly equal halves are identified as highly important. This process is repeated recursively, creating a hierarchy of node importance.

Once this hierarchy is established, a bi-directional search can be performed, but it's constrained to only move up the hierarchy from both directions. This drastically limits the search space.

To ensure that the shortest path is always found, even with this hierarchical search, shortcuts are introduced. These are artificial edges added between nodes that represent the shortest path using only lower-ranked nodes. This prevents the algorithm from missing a shorter route that might involve local roads, even if the hierarchical search initially bypasses it.

This entire process, combining hierarchical ordering, bi-directional search, and shortcuts, is known as a Customizable Contraction Hierarchy (CCH).

The Speed of Modern Mapping

The CCH approach breaks down into three phases:

  1. Ordering Nodes and Adding Shortcuts: This is the most computationally intensive part, done once unless the road network changes significantly. For North America, this might take around 1 hour and 40 minutes.
  2. Calculating Shortcut Weights: This step is rerun when traffic updates occur and needs to be relatively fast, taking seconds to minutes.
  3. The Actual Search: This is the query phase, which needs to be incredibly fast.

On the North American network, a well-tuned Dijkstra might take around seven seconds and explore most of the 64 million nodes. In contrast, a CCH can find the shortest path in approximately 200 microseconds – that's 35,000 times faster, exploring only about 1,450 nodes. This is the kind of speed that allows map applications to provide near-instantaneous directions.

Simplicity and Reliability

The enduring success of Dijkstra's algorithm, even as the foundation for highly complex systems like CCH, speaks to its fundamental elegance. Dijkstra himself believed that "simplicity is prerequisite for reliability." He understood that ultimately, programmers are accountable for their work, not the machines. His hope was that his emphasis on thoughtful design would serve as a lasting legacy, encouraging others to approach problems with the same rigor and elegance.

Key Takeaways