OASIcs.ATMOS.2011.52.pdf
- Filesize: 435 kB
- 12 pages
Document
Faster Batched Shortest Paths in Road Networks
Authors
-
Part of:
Volume:
11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2011)
Series: Open Access Series in Informatics (OASIcs)
Conference: Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS) - License:
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
- Publication Date: 2011-09-19
Cite As Get BibTex
Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. Faster Batched Shortest Paths in Road Networks. In 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 20, pp. 52-63, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)
https://doi.org/10.4230/OASIcs.ATMOS.2011.52
Abstract
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.
Subject Classification
Keywords
- shortest paths
- contraction hierarchies
- many-to-many
- one-to-many
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads