## May 20, 2016:

#
A Sidetrack-based Approach for the k Shortest Simple Path Problem

##
Denis Kurz

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