[dbatten]

If you find this interesting, definitely consider checking out contraction hierarchies. One of the early algorithms used by mapping software to enable calculating fastest routes between any pair of places. It's exact, and it's orders of magnitude faster than graph search algorithms like Dijkstra.

This webpage has a very intuitive graphical explanation of how it works: https://www.mjt.me.uk/posts/contraction-hierarchies/

(I had the joy of implementing this in Python with OSM data a few years ago. Planning a three hour car trip with software I wrote and having it come back with the same path recommended by Google Maps in a matter of milliseconds was a very rewarding feeling.)