From Dijkstra to Google Maps: How Shortest-Path Algorithms Work

The evolution of shortest-path algorithms is explained, from Edsger Dijkstra's 1956 method to modern map-routing techniques used by navigation systems. Visual examples and historical context show why different algorithms are suited to different constraints and graph sizes.

■ Foundations
- The shortest-path problem, brute-force limits, and breadth-first search
- Dijkstra's algorithm, weighted graphs, the ARMAC demonstration, and publication history

■ Optimized search
- A-star heuristics, bi-directional search, and distance vs. travel-time trade-offs
- Early GPS road hierarchies and pre-processing trade-offs

■ Scalable routing
- Nested dissection, node ranking, shortcuts, and customizable contraction hierarchies
- Applications in games and mapping, plus Dijkstra's lasting influence

Viewers interested in computer science, algorithms, navigation software, or game development can gain a conceptual understanding of how route planning works and which approaches address which challenges.