Problem Detail:
Definition. Given a graph $G=(V,E)$ and two vertices $s$ and $t$, the $k$-shortest-paths problem is finding the $k$ shortest simple paths between $s$ and $t$ in $G$.
Note that the length of these paths is not necessarily equal, and vertices $s$ and $t$ are necessarily $k$-connected. I was wondering if there is a linear time (in terms of $n$ and $m$) algorithm for this problem. I have looked at a few papers in the literature, such as “A New Implementation Of Yen’s Ranking Loopless Paths Algorithm” but the time complexity is really high $O(Kn(m+nlogn))$. Also, the other paper by Epstein “Finding the k shortest paths” presents an algorithm that finds the $k$ shortest paths that are not necessarily simple paths with running time $O(n+m+k)$. Is there a linear-time algorithm for the $k$-simple-shortest-paths problem?
Asked By : emab
Answered By : Carlos Linares López
First of all, the answer that applies here was already given by Raphael in the comments to the question: “Given that we don’t even know how to find one simple shortest path in linear time, I doubt it.” In the following, thus, I will assume you are interested in knowing about the best available algorithms in the current state of the art. In the following, I describe the best worst-case bound (to the best of my knowledge) but also an algorithm that might run in linear time in some specific cases. But before describing the latest developments in the state of the art, I wanted to emphasize the importance of simple paths in this specific problem. As a matter of fact, many people overlooks the importance of this requirement and some do not even understand it at first glance. When computing the shortest path from a start vertex to a goal vertex, the optimal path is necessarily simple, i.e., it does not repeat any vertices. However, when computing $k$ optimal paths, the second, third, … best paths might not be simple. To prove it, I provide here an example that has been slightly adapted from Hershberger, Maxel & Suri, 2007: 
The Figure shows a digraph whose optimal solution (from the source vertex $s$ to the goal vertex $t$) is the path $pi_1 : langle s, A, B, C, D, trangle$ with a cost equal to 5. If paths are not required to be simple, then the second and third optimal paths are $pi_2 : langle s, A, B, C, D, C, D, trangle$ and $pi_3 : langle s, A, B, A, B, C, D, trangle$ both with a cost equal to 7. However, if paths are required to be simple, then the second and third optimal paths would be $pi_2 : langle s, F, trangle$ and $pi_3 : langle s, G, trangle $ with costs 10 and 11, respectively. Given a graph $G(V, E)$ where $V$ is the set of vertices and $langle u, vranglein E, u, vin V$ if there is an edge between vertices $u$ and $v$, the current state of the art for this problem to the best of my knowledge is described below: The first significant improvement to solve the $k$ optimal paths problem is Eppstein’s algorithm (Eppstein, 1998) which runs in $O(|E|+|V|log |V|+k)$. However, this algorithm requires the graph to be given explicitly. $K^*$ alleviates this requirement while maintaining the low complexity (Aljazzar & Leue, 2011) and, additionally, enables the application of admissible heuristics. In both cases, the output computed by these algorithms are not necessarily simple paths. In case that paths are required to be simple, the best results is due to Yen (Yen, 1971, 1972), generalized later by Lawler (Lawler, 1972), which using modern data structures can be implemented in $O(k|V|(|E|+|V|log |V|))$ worst-case time. In the case of undirected graphs, Katoh, Ibaraki and Mine (Katoh, Ibaraki & Mine, 1982) improve Yen’s algorithm to $O(k(|E|+|V|log |V|))$ time. While Yen’s asymptotic worst-case bound for enumerating $k$ simple shortest paths in a directed graph remains unbeaten (again, to the best of my knowledge!), several attempts have been done to outperform it in practice. One of such works is due to John Hershberger et al., who introduced a replacement paths algorithm which is known to fail scarcely. As a result, their algorithm delivers a speedup that grows linearly with the average number of edges in the $k$ shortest paths but, for some cases (as random graphs), this speedup is minimized. Hope this helps, Bibliography Aljazzar, H. & Leue, S. (2011). $K^*$: A heuristic search algorithm for finding the $k$ shortest paths. Artificial Intelligence, 175(18), 2129-2154. Eppstein, D. (1998). Finding the $k$ shortest paths. SIAM Journal on Computing, 28(2), 652-673. Hershberger, J., Maxel, M. & Suri, S. (2007). Finding the $k$ shortest simple paths: A new algorithm and its implementation. ACM Transactions on Algorithms, 3(4), 45-46 Katoh, N., Ibaraki, T. & Mine, H. (1982). An efficient algorithm for $k$ shortest simple paths. Networks, 12, 411-427. Lawler, E. L. (1972). A procedure for computing the $k$ best solutions to discrete optimization problems and its application to the shortest path problem. Management Science, 18, 401-405. Yen, J.Y. (1971). Finding the $k$ shortest loopless paths in a network. Management Sciences, 17, 712-716. Yen, J.Y. (1972). Another algorithm for finding the $k$ shortest loopless network paths. Proceedings of 41st Management Operations Research Society of America, 20.
The Figure shows a digraph whose optimal solution (from the source vertex $s$ to the goal vertex $t$) is the path $pi_1 : langle s, A, B, C, D, trangle$ with a cost equal to 5. If paths are not required to be simple, then the second and third optimal paths are $pi_2 : langle s, A, B, C, D, C, D, trangle$ and $pi_3 : langle s, A, B, A, B, C, D, trangle$ both with a cost equal to 7. However, if paths are required to be simple, then the second and third optimal paths would be $pi_2 : langle s, F, trangle$ and $pi_3 : langle s, G, trangle $ with costs 10 and 11, respectively. Given a graph $G(V, E)$ where $V$ is the set of vertices and $langle u, vranglein E, u, vin V$ if there is an edge between vertices $u$ and $v$, the current state of the art for this problem to the best of my knowledge is described below: The first significant improvement to solve the $k$ optimal paths problem is Eppstein’s algorithm (Eppstein, 1998) which runs in $O(|E|+|V|log |V|+k)$. However, this algorithm requires the graph to be given explicitly. $K^*$ alleviates this requirement while maintaining the low complexity (Aljazzar & Leue, 2011) and, additionally, enables the application of admissible heuristics. In both cases, the output computed by these algorithms are not necessarily simple paths. In case that paths are required to be simple, the best results is due to Yen (Yen, 1971, 1972), generalized later by Lawler (Lawler, 1972), which using modern data structures can be implemented in $O(k|V|(|E|+|V|log |V|))$ worst-case time. In the case of undirected graphs, Katoh, Ibaraki and Mine (Katoh, Ibaraki & Mine, 1982) improve Yen’s algorithm to $O(k(|E|+|V|log |V|))$ time. While Yen’s asymptotic worst-case bound for enumerating $k$ simple shortest paths in a directed graph remains unbeaten (again, to the best of my knowledge!), several attempts have been done to outperform it in practice. One of such works is due to John Hershberger et al., who introduced a replacement paths algorithm which is known to fail scarcely. As a result, their algorithm delivers a speedup that grows linearly with the average number of edges in the $k$ shortest paths but, for some cases (as random graphs), this speedup is minimized. Hope this helps, Bibliography Aljazzar, H. & Leue, S. (2011). $K^*$: A heuristic search algorithm for finding the $k$ shortest paths. Artificial Intelligence, 175(18), 2129-2154. Eppstein, D. (1998). Finding the $k$ shortest paths. SIAM Journal on Computing, 28(2), 652-673. Hershberger, J., Maxel, M. & Suri, S. (2007). Finding the $k$ shortest simple paths: A new algorithm and its implementation. ACM Transactions on Algorithms, 3(4), 45-46 Katoh, N., Ibaraki, T. & Mine, H. (1982). An efficient algorithm for $k$ shortest simple paths. Networks, 12, 411-427. Lawler, E. L. (1972). A procedure for computing the $k$ best solutions to discrete optimization problems and its application to the shortest path problem. Management Science, 18, 401-405. Yen, J.Y. (1971). Finding the $k$ shortest loopless paths in a network. Management Sciences, 17, 712-716. Yen, J.Y. (1972). Another algorithm for finding the $k$ shortest loopless network paths. Proceedings of 41st Management Operations Research Society of America, 20. Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/60355 Ask a Question Download Related Notes/Documents
