2026-07-20T11:15:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3266 2024-03-06T10:28:55Z ddc:004 open_access

Faster Batched Shortest Paths in Road Networks Delling, Daniel Goldberg, Andrew V. Werneck, Renato F. shortest paths contraction hierarchies many-to-many one-to-many 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Daniel Delling and Andrew V. Goldberg and Renato F. Werneck 2011 Is Part Of OASIcs, Volume 20, 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2011) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2011.52 urn:nbn:de:0030-drops-32663 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2011.52 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode