K-Shortest Simple Paths Using Biobjective Path Search
- 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): | Mathematical Programming Computation |
| Volume: | 17 |
| First Page: | 349 |
| Last Page: | 384 |
| Year of first publication: | 2025 |
| ArXiv Id: | http://arxiv.org/abs/2309.10377 |
| DOI: | https://doi.org/10.1007/s12532-025-00276-0 |
| Licence (German): | Creative Commons - CC BY-NC-ND - Namensnennung - Nicht kommerziell - Keine Bearbeitungen 4.0 International |


