Distances and shortest paths on graphs of bounded highway dimension: simple, fast, dynamic

Sébastien Collette, John Iacono

Dijkstra's algorithm is the standard method for computing shortest paths on arbitrary graphs. However, it is slow for large graphs, taking at least linear time. It has been long kn…