Veritasium
May 30, 2026
TL;DR
Modern navigation apps use advanced algorithms based on Dijkstra's 1956 shortest-path invention, optimized through techniques like A-star, bidirectional search, and contraction hierarchies to find routes 35,000 times faster than the original method.
“One morning I was shopping in Amsterdam with my young fiance, and tired, we sat down on the cafe terrace to drink a cup of coffee. And I was just thinking about whether I could do this.”
— Edsger Dijkstra
“It was a 20-minute invention. I designed it without pencil and paper. I learned later that one of the advantages of designing without pencil and paper is that you are almost forced to avoid all avoidable complexities.”
— Edsger Dijkstra
“Simplicity is prerequisite for reliability.”
— Edsger Dijkstra
“If 10 years from now, when you're doing something quick and dirty, you suddenly visualize that I'm here, looking over your shoulders, and say to yourself, 'Dijkstra would not have liked this.' Well, that'd be enough immortality for me.”
— Edsger Dijkstra
1. The Problem: 64 Million Intersections
Finding the shortest route among 64 million North American road intersections presents 10^220 possible routes. Even checking a billion routes per second would take 10^200 years, yet Google Maps solves it in 4 seconds.
2. Dijkstra's Invention: A 20-Minute Coffee Break Idea
In 1956 Amsterdam, computer scientist Edsger Dijkstra needed a compelling demo to prove computers were useful. He invented the shortest-path algorithm during a café visit, which became one of computer science's cornerstones. The algorithm assigns costs to nodes and explores in order of lowest cost, guaranteeing the shortest path.
3. Breadth-First Search vs. Weighted Graphs
Simple breadth-first search treats all roads equally and finds shortest paths in unweighted graphs. However, real roads have varying distances (weights), requiring a smarter approach that Dijkstra solved by tracking minimum cost to each node.
4. A-Star: Adding Direction with Heuristics
A-star improves Dijkstra by penalizing exploration away from the target using heuristics (e.g., straight-line distance). This focuses search toward the destination, cutting explored nodes by 10x, making it popular for video game AI and maze-solving.
5. Bidirectional Search: Halving the Frontier
Running simultaneous Dijkstra searches from both source and target reduces the search frontier area by half. A Carnegie Hall to Wall Street query dropped from 7,200 nodes to 2,600 nodes explored, a 3x improvement.
6. Road Hierarchy: Exploiting Structure with Preprocessing
Early GPS systems manually categorized roads into hierarchies (highway, major local, narrow). Bidirectional search prioritizes higher hierarchies first, reducing search area. However, incorrect hierarchy boundaries risk missing optimal local-road routes.
7. Nested Dissection: Automatic Hierarchy Discovery
Instead of manual road classification, nested dissection automatically ranks nodes by importance—identifying bottlenecks like river crossings that split the graph in half. The Mississippi River's 102 bridges rank highest on the North American network.
8. Contraction Hierarchies: Shortcuts and Guarantees
By contracting nodes from lowest to highest rank, the algorithm adds shortcuts representing shortest paths through lower-ranked nodes. This prevents missing optimal routes while limiting search to high-rank nodes, balancing speed with correctness.
9. Customizable Contraction Hierarchies: Three-Phase Optimization
Phase 1 (preprocessing, ~100 min) ranks nodes and adds shortcuts. Phase 2 (traffic updates, ~1 sec) recalculates shortcut weights. Phase 3 (queries, <1 millisecond) performs bidirectional search. This achieves 35,000x speedup and explores only 1,450 nodes on average.
10. Legacy and Impact: Simplicity as Foundation
Dijkstra's algorithm, now 70 years old, remains the core of modern routing. Its elegance and simplicity made it reliable and extensible; subsequent breakthroughs build on its principles, proving that thoughtful, constraint-free design yields timeless solutions.