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

Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck

Abstract

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.

Details

Publication typeTechReport
NumberMSR-TR-2010-165
> Publications > A Hub-Based Labeling Algorithm for Shortest Paths on Road Networks