We propose an algorithm for the problem of finding the k shortest simple s-t paths in a directed, weighted graph. Unlike other algorithms for this problem, it does not solve the replacement path problem repeatedly. Instead, we exploit the notion of sidetracks of a shortest path trees. Sidetracks were first used by Eppstein to solve a similar problem where the output paths are not required to be simple.
Our algorithm maintains the worst case running time of state-of-the-art algorithms for this problem. In practice, the sidetrack-based approach is highly competitive on all graph classes that we used in computational studies compared to other approaches, and faster by up to two orders of magnitude on some of the classes.Joint work with Petra Mutzel