K-Shortest Simple Paths Using Biobjective Path Search
under review
- In this paper we introduce a new algorithm for the k-Shortest Simple Paths (K-SSP) problem with an asymptotic running time matching the state of the art from the literature. It is based on a black-box algorithm due to Roditty and Zwick (2012) that solves at most 2k instances of the Second Shortest Simple Path (2-SSP) problem without specifying how this is done. We fill this gap using a novel approach: we turn the scalar 2-SSP into instances of the Biobjective Shortest Path problem. Our experiments on grid graphs and on road networks show that the new algorithm is very efficient in practice.
Author: | Pedro Maristany de las Casas, Antonio Sedeño-Noda, Ralf Borndörfer, Max Huneshagen |
---|---|
Document Type: | Article |
Parent Title (English): | Arxiv Preprint |
Year of first publication: | 2023 |
ArXiv Id: | http://arxiv.org/abs/2309.10377 |
DOI: | https://doi.org/10.48550/arXiv.2309.10377 |
Licence (German): | Creative Commons - CC BY-NC-ND - Namensnennung - Nicht kommerziell - Keine Bearbeitungen 4.0 International |