On the k Shortest Simple Paths Problem Using Biobjective Search

The k simple shortest paths problem (kSSP) on a simple weighted digraph is a classic combinatorial problem. Although Yen’s algorithm no longer possesses the best known time complexity, it remains an important benchmark for kSSP algorithms. Roditty and Zwick developed a kSSP algorithm that solves the problem by solving 2k instances of 2SSP. However, the authors do not specify how to solve this subroutine efficiently. We close this gap by providing a new biobjective search algorithm for 2SSP. The algorithm by Roditty and Zwick in conjunction with our new algorithm matches the running time bound of Yen’s algorithm and is fast in practice. Moreover, we discuss the framework of the asymptotically fastest kSSP algorithm due to Gotthilf and Lewenstein and use it in connection with a recent breakthrough result on the all pairs shortest paths problem by Orlin and Végh to show the existence of an O(kmn) algorithm for kSSP for integer costs. This improved time complexity bound is the best known for this relevant special case. In our computational experiments on road and grid graphs we assess the new algorithm’s practical efficiency. It turns out to be significantly faster than Yen’s algorithm on these graphs.