An Empirical Comparison of k-Shortest Simple Path Algorithms on Multicores
Deepak Ajwani, Erika Duriakova, Neil Hurley, Ulrich Meyer, Alexander Schickedanz · 2018
We consider the loop less k-shortest path (KSP) problem. Although this problem has been studied in the sequential setting for at least the last two decades, no good parallel implementations are known. In this paper, we provide (i) a first systematic empirical comparison of various KSP algorithms and heuristic optimisations, (ii) carefully engineer various parallel implementations of these sequential algorithms and (iii) perform an extensive study of these parallel implementations on a range of graph classes and multicore architectures to determine the best algorithm and parallelization strategy for different graph classes.