2014/11/25 by Rizzi, Romeo, Sacomoto, Gustavo, Sagot, Marie-France · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1411.6852
The problem of listing the K shortest simple (loopless) st-paths in a graph has been studied since the early 1960s. For a non-negatively weighted graph with n vertices and m edges, the most efficient solution is an O(K(mn + n2 log n)) algorithm for directed graphs by Yen and Lawler [Management Science, 1971 and 1972], and an O(K(m+n log n)) algorithm for the undirected version by Katoh et al. [Networks, 1982], both using O(Kn + m) space. In this work, we consider a different parameterization for this problem: instead of bounding the number of st-paths output, we bound their length. For the bounded length parameterization, we propose new non-trivial algorithms matching the time complexity of the classic algorithms but using only O(m+n) space. Moreover, we provide a unified framework such that the solutions to both parameterizations -- the classic K-shortest and the new length-bounded paths -- can be seen as two different traversals of a same tree, a Dijkstra-like and a DFS-like traversal, respectively.