Refine
Year of publication
- 2025 (1)
Document Type
- Article (1)
Language
- English (1)
Has Fulltext
- yes (1)
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.
