Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
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. They also analyze a labeling algorithm. While no practical implementation of this algorithm existed, it has the best time bounds. This paper describes an implementation of the labeling algorithm that is faster than any existing method on continental road networks.

Details

Publication typeInproceedings
Published inProceedings of the 10th International Symposium on Experimental Algorithms (SEA'11)
SeriesLecture Notes in Computer Science
PublisherSpringer Verlag
> Publications > A Hub-Based Labeling Algorithm for Shortest Paths on Road Networks