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 highly practical and intuitive, but until recently there was no theoretical explanation of their practical 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, which is a strengthening of the doubling dimension. The analysis gives good bounds for networks with low highway dimension. Our analysis explores an unexpected relationship to VC-dimension, which leads to better algorithms.

We also show that the hub labeling algorithm achieves a better theoretical time bound. This motivates a heuristic implementation of this algorithm. Our experimenters show that the implementation outperforms the fastest previous codes, validating the theoretical prediction.

Joint work with Ittai Abraham, Daniel Delling, Amos Fiat, and Renato Werneck.