K-Shortest Simple Paths Using Biobjective Path Search

In this paper we introduce a new algorithm for the k-Shortest Simple Paths (k) 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 <cit.> that solves at most 2k instances of the Second Shortest Simple Path (2) problem without specifying how this is done. We fill this gap using a novel approach: we turn the scalar 2 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset