A Hub-Based Labeling Algorithm for Shortest Paths on Road Networks

  • Ittai Abraham
  • Daniel Delling
  • Andrew Goldberg
  • Renato Werneck

MSR-TR-2010-165 |

Abraham et al. [SODA 2010] have recently presented a theoretical analysis of several practical point-to-point shortest path algorithms based on modeling road networks as graphs with low highway dimension. Among the methods they analyzed, the one with the best time bounds is the labeling algorithm. Their results suggest that the algorithm is interesting from a theoretical viewpoint, but leave open the existence of a practical implementation. This paper presents such an implementation and shows experimental evidence that it is actually faster than the fastest method previously studied.