@article{MaristanydelasCasasSedenoNodaBorndoerferetal., author = {Maristany de las Casas, Pedro and Sede{\~n}o-Noda, Antonio and Bornd{\"o}rfer, Ralf and Huneshagen, Max}, title = {K-Shortest Simple Paths Using Biobjective Path Search}, series = {Arxiv Preprint}, journal = {Arxiv Preprint}, doi = {10.48550/arXiv.2309.10377}, abstract = {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.}, language = {en} }