How Does Google Maps Actually Work?

Summary of technological concepts & product/research analysis (from auto-subtitles)

Why shortest-path is hard at map scale

• Driving/navigation is modeled as a graph with millions of intersections (e.g., ~64 million nodes in North America).
• Brute-force checking of all candidate routes is infeasible:
  • Even with extremely fast checking, it would take centuries.
• Yet Google/Apple Maps can answer quickly (the video contrasts seconds on-device vs sub-millisecond performance at Google scale while serving many users).

Core shortest-path algorithms explained

Breadth-First Search (BFS) (simplified shortest path when all edges equal)

• Treats all roads as the same length.
• Explores neighbors level-by-level until the target is found.
• Guarantees the fewest “steps,” not the true shortest distance when edge lengths differ.

Dijkstra’s Algorithm (weighted shortest path)

• Maintains:
  • costs: shortest known distance/time from the source to every node
  • exploration of nodes in increasing current cost
• Updates node costs whenever a shorter path is discovered.
• Correctness intuition:
  • When the target is the lowest-cost unexplored node, the shortest path has been found.
• Practical performance issue:
  • On large road graphs, Dijkstra can require exploring a huge fraction of nodes (shown as seconds per query in experiments).
  • Also compared against a mobile runtime (~4 seconds).

How Maps gets faster: heuristics, bi-directional search, and road hierarchy

A* (A-star): heuristic guidance toward the target

• Uses Dijkstra-like exploration but prioritizes nodes by:
  • cost so far + heuristic estimate
• The heuristic is often:
  • straight-line distance, or
  • estimated travel time
• Visualization described:
  • The heuristic is shown like a “3D height” surface—farther from the destination means higher penalty.
• Benefits:
  • Often explores far fewer nodes (example: ~7,000 nodes checked, about 10× improvement vs Dijkstra for distance).
• Trade-offs / limitations:
  • If optimizing for travel time rather than geometric distance, the heuristic may underestimate too aggressively.
  • Then A can do worse than well-tuned Dijkstra because it must evaluate more heuristic logic (including computational overhead like square roots*).

Bi-directional Dijkstra

• Runs Dijkstra from source and target simultaneously.
• Reduces explored area because the two search frontiers overlap.
• Example shown:
  • Carnegie Hall → Wall Street:
    • Dijkstra explores ~7,200 nodes
    • Bi-directional explores ~2,600 nodes (≈ 3× improvement)

Why these still miss “human road intuition”

• Standard algorithms don’t encode that road networks have hierarchy:
  • local roads → highways → local roads
• As a result, they can waste time exploring many local roads even when highways are likely optimal.

Road hierarchy + multi-level search (early GPS idea)

• The 1990s in-car GPS implementations used pre-computed road classes (hierarchies).
• Approach described:
  • Run bi-directional Dijkstra starting from a “narrow road” level inside a candidate area
  • If not found, move up to major roads, then highways
  • Searches overlap at some hierarchy level to return the path
• Downsides noted:
  • Hard to define hierarchy levels correctly without risking missed shortest paths
  • Candidate-area tuning can trade correctness vs performance

Modern speed idea: Customizable Contraction Hierarchies (CH)

The video presents a likely middle ground between:

• massive precomputed lookup tables (fast queries, huge storage/build costs), and
• pure Dijkstra (no preprocessing, slow queries)

The goal

• Achieve very fast query times (target: far below a millisecond), while keeping preprocessing manageable.

Phase-based CH design (as described)

1. Phase 1: Preprocess (expensive)

   • Perform nested dissection to rank nodes by importance.
   • Key concept:
     • nodes that “split the graph” (e.g., major bridges across the Mississippi) get high rank
   • Automatically build a hierarchy (no manual road-class annotation).
   • Add shortcuts via “lower triangles” to preserve shortest-path correctness while enabling searches that only move “up” the hierarchy.

2. Phase 2: Customization (re-run when traffic changes)

   • Recompute shortcut weights to reflect current conditions.
   • The video suggests this is a relatively quick rerun when traffic updates occur.

3. Phase 3: Query (very fast)

   • Search from source and target up the hierarchy until they meet.
   • Use shortcuts so the algorithm avoids traversing every low-level edge.

Performance figures from the experiment

• North America:
  • Dijkstra: ~7 seconds per long-distance path (benchmark described)
  • Customizable Contraction Hierarchy: ~200 microseconds per query (configuration-dependent; possibly ~100 µs)
• Reported scale improvements:
  • ~35,000× faster than Dijkstra in the experiment
  • Average explored nodes: about 1,450 nodes (vs exploring most/all nodes with Dijkstra)
  • Search space reduction factor: around 44,000 in the example described

Handling shortcut correctness vs hierarchy quality

• The method can tolerate imperfect node rankings:
  • If a shortest path would require lower-ranked nodes, shortcuts added during preprocessing preserve correctness.
• But poor configurations can reduce efficiency:
  • A bad contraction order can increase shortcuts and force the algorithm to explore nearly everything (example described).

Why this still connects to Dijkstra

• The video emphasizes CH is “still Dijkstra in the core”:
  • it uses Dijkstra-like shortest-path logic, but with heavy preprocessing and constrained hierarchical search.

Sponsorship / tutorial component (coding + learning)

• The creator mentions testing these ideas using:
  • Python scripts
  • OpenStreetMaps data
• A sponsor segment (Boot.dev) promotes:
  • courses with hands-on problems (including graph algorithms like Dijkstra)
  • learning for backend/DevOps skills and tools (e.g., Go, Docker, Linux, AWS)
• Framing:
  • a “how to learn the under-the-hood journey” for pathfinding.

Main speakers/sources (as named in subtitles)

• Derek (main host/explainer)
• Henry (additional commentator/insight, including algorithm comparisons)
• Casper (portraying/quoting Dijkstra impression)
• Edsgar Dijkstra (historical source; quoted via scripted readings)
• Ben (mentioned as testing CH on North America)
• Mikkel Thorup (historical/theoretical mention; shortest-path research context)
• 2swap (partner channel providing simulations/animations of the algorithm steps)
• Polylog (mentioned for visualization help)