Faster Batched Shortest Paths in Road Networks
Daniel Delling, Andrew V. Goldberg, Renato F. Werneck · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2011
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.