Improved algorithms for the k simple shortest paths and the replacement paths problems
Given a directed, non-negatively weighted graph G = (V, E) and S, t is an element of V, we consider two problems. In the k simple shortest paths problem, we want to find the k simple paths from s to t with the k smallest weights. In the replacement paths problem. we want the shortest path from s to t that avoids e, for every edge e in the original shortest path from s to t. The best known algorithm for the k simple shortest paths problem has a running of O(k(mn + n(2) log n)). For the replacement paths problem the best known result is the trivial one running in time O(mn + n(2) log n). In this paper we present two simple algorithms for the replacement paths problem and the k simple shortest paths problem in weighted directed graphs (using a solution of the All Pairs Shortest Paths problem). The running time of our algorithm for the replacement paths problem is O(mn + n(2) log log n). For the k simple shortest paths we will perform O(k) iterations of the second simple shortest path (each in O(mn+n(2) log log n) running time) using a useful property of Roditty and Zwick [L. Roditty, U. Zwick, Replacement paths and k simple shortest paths in unweighted directed graphs, in: Proc. of International Conference on Automata, Languages and Programming (ICALP), 2005, pp. 249-260]. These running times immediately improve the best known results for both problems over sparse graphs. Moreover, we prove that both the replacement paths and the k simple shortest paths (for constant k) problems are not harder than APSP (All Pairs Shortest Paths) in weighted directed graphs. (C) 2008 Published by Elsevier B.V.
algorithms k simple shortest paths shortest paths replacement paths weighted directed graphs