Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Faster Batched Shortest Paths in Road Networks

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


We study the problem of computing batched shortest paths in road networks efficiently. Our focus is on computing paths from a single source to multiple targets (one-to-many queries). We perform a comprehensive experimental comparison of several approaches, including new ones. We conclude that a new extension of PHAST (a recent one-to-all algorithm), called RPHAST, has the best performance in most cases, often by orders of magnitude. When used to compute distance tables (many-to-many queries), RPHAST often outperforms all previous approaches.


Publication typeInproceedings
Published inProceedings of the 11th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'11)
PublisherOpenAccess Series in Informatics
> Publications > Faster Batched Shortest Paths in Road Networks