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 liter- ature. It is based on a black-box algorithm due to Roditty and Zwick [30] 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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Pedro Maristany de las Casas, Antonio Sedeño-Noda, Ralf Borndörfer, Max Huneshagen
DOI:https://doi.org/10.1007/s12532-025-00276-0
ISSN:1867-2949
Parent Title (English):Mathematical Programming Computation
Publisher:Springer Science and Business Media LLC
Document Type:Article
Language:English
Year of Completion:2025
Volume:17
Issue:2
Page Number:36
First Page:349
Last Page:384
Mathematical Programming Computation :MPC 2025 - Issue 2
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.