We present an overview of recent algorithms for computing point-to-point shortest paths, with an emphasis on road networks. In its simplest form, the problem can be solved in essentially linear time by the well-known algorithm of Dijkstra. Unfortunately, this is too slow for continental-sized maps. Two-stage algorithms can do much better: after spending a reasonable amount of time preprocessing the network, they can answer online queries several orders of magnitude faster than Dijkstra's algorithm. We cover not only on the main algorithmic ideas of various methods, but also the engineering challenges. Seemingly minor implementation details can be the difference between practical and impractical solutions in the real world.

List of topics

* Dijkstra's algorithm
* Basic data structures
* Bellman-Ford-Moore and its variants
* A* search and landmarks
* Reach-based routing
* Contraction Hierarchies
* Transit node routing
* Arc Flags
* Extensions: the dynamic and time-dependent cases
* Highway dimension