Highway Dimension, Shortest Paths, and Provably Efficient Algorithms

  • Ittai Abraham ,
  • Amos Fiat ,
  • Andrew Goldberg ,
  • Renato Werneck

Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA10) |

Published by Society for Industrial and Applied Mathematics

Computing driving directions has motivated many shortest path heuristics that answer queries on continental scale networks, with tens of millions of intersections, literally instantly, and with very low storage overhead. In this paper we complement the experimental evidence with the first rigorous proofs of efficiency for many of the heuristics suggested over the past decade. We introduce the notion of highway dimension and show how low highway dimension gives a united explanation for several seemingly different algorithms.