If you’ve studied routing algorithms, you’ve come across Edsger Dijkstra’s algorithm, a fundamental method for finding the shortest paths between nodes in a graph or network. This on its surface very simple algorithm has had a profound impact and has been widely used in various applications, from navigation aids to GIS.
In their most recent video, “How does Google Maps actually work?”, popular science YouTube channel Veritasium explores the origin of Dijkstra’s algorithm, how it laid the groundwork for modern routing techniques used in wayfinding apps and how techniques such as Nested Dissection and Customisable Contraction Hierarchies enable microsecond response times for route queries in large road networks: