Veritasium
May 30, 2026
How Navigation Algorithms Find the Shortest Route in Seconds
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.
Key Takeaways
- 1Dijkstra's algorithm, invented in 1956 during a coffee break in Amsterdam, revolutionized pathfinding by systematically exploring nodes in order of lowest cost, guaranteeing the shortest path.
- 2A-star improves upon Dijkstra by using a heuristic (straight-line distance to target) to prioritize exploration toward the goal, reducing search space by 10x in city-scale problems.
- 3Bidirectional search halves the search frontier by running simultaneous searches from source and target, achieving 3x speedups on some graphs.
- 4Contraction hierarchies leverage road network hierarchy by ranking nodes by importance (major bottlenecks like river crossings ranked highest), enabling queries 35,000x faster than basic Dijkstra.
- 5Modern routing requires 'customizable' contraction hierarchies in three phases: preprocessing node rankings (expensive, infrequent), updating shortcut weights for traffic (seconds), and executing queries (under 1 millisecond).
- 6The Mississippi River's limited bridges create critical bottlenecks in North America's road network, becoming the highest-ranked nodes that all coast-to-coast routes must traverse.
- 7Simplicity and thoughtful design are foundational to reliable algorithms; Dijkstra's enduring legacy stems from solving a demonstrable real-world problem elegantly without mathematical jargon.
Notable Quotes
“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
Chapters
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.
Key People & Entities
- Edsger Dijkstra
- Dutch computer scientist who invented Dijkstra's algorithm in 1956 during a café visit in Amsterdam; created one of computer science's most foundational shortest-path algorithms.
- ARMAC
- Early computer developed at the Mathematical Center in the Netherlands for which Dijkstra designed his algorithm as a demonstration of computational power.
- Mikkel Thorup
- Danish computer scientist who noted in the 1990s that all theoretical developments in shortest-path algorithms have been based on Dijkstra's work.
- Google Maps / Apple Maps
- Navigation applications that employ advanced routing algorithms (likely including contraction hierarchies) to compute optimal routes in milliseconds.
- Boot.dev
- Online programming education platform offering courses in backend, DevOps, and pathfinding algorithms; sponsor of the video.
Glossary
- Dijkstra's Algorithm
- A shortest-path algorithm that explores nodes in order of lowest cost from a source, guaranteeing the shortest path to any target by checking all lower-cost paths first.
- Breadth-First Search (BFS)
- A graph-traversal algorithm that explores all nodes at distance k before exploring nodes at distance k+1, finding shortest paths in unweighted graphs.
- A-Star (A*)
- A pathfinding algorithm combining Dijkstra's cost-tracking with a heuristic (e.g., straight-line distance) to prioritize exploration toward the target, reducing search space.
- Heuristic
- An estimated value (like straight-line distance to goal) used to guide algorithm decisions, improving efficiency without guaranteeing optimality.
- Bidirectional Search
- A technique running simultaneous searches from both source and target toward each other, reducing the overall search frontier and exploration time.
- Nested Dissection
- A preprocessing method that recursively partitions a graph to identify bottleneck nodes (those splitting the graph roughly in half) and rank them by importance.
- Contraction Hierarchy
- An algorithm structure that assigns node ranks and adds shortcuts during preprocessing, enabling bidirectional search to explore only high-ranked nodes while maintaining shortest-path guarantees.
- Shortcuts
- Artificial edges added during preprocessing that represent shortest paths through lower-ranked nodes, ensuring optimal routes aren't missed despite limited high-rank search.
- Graph
- A data structure of nodes (cities/intersections) connected by edges (roads), used to represent networks and enable pathfinding algorithms.
- Cost/Weight
- A numerical value assigned to an edge representing distance, time, or other metrics; algorithms minimize total cost along a path.