Computing driving directions has motivated many shortest path heuristics that answer queries on continental-scale networks, with tens of millions of intersections, in real time. The underlying algorithms are intuitive, but until recently there was no theoretical explanation of their performance. We review some of these algorithms and give the first theoretical analysis for them on a non-trivial class of networks.

For our analysis, we introduce the notion of highway dimension. The analysis works for networks with low highway dimension and gives a unified explanation of algorithms' good performance. Our analysis explores an unexpected relationship to VC-dimension and learning theory and applies the latter to graph algorithm design.

We also propose a new algorithm that achieves better theoretical time bounds on queries and is in the spirit of labeling routing algorithms from the distributed computing literature. Our recent experiments show that an implementation of this algorithm is extremely fast in practice, validating the theoretical prediction.
Joint work with Ittai Abraham, Amos Fiat, and Renato Werneck