Finding the k-shortest path between two nodes

Problem Detail: 

Given a weighted digraph $G=V,E$, and a weight function, $d(u,v)$, one can normally use Dijkstra's algorithm to obtain the shortest path. What I am interested in, is how to obtain the $2^{nd}$-shortest path, the $3^{rd}$-shortest, and so on.

Questions:

Is there an efficient algorithm to get the i-th-most-shortest-path between two nodes in a weighted graph?

Is there an efficient algorithm to get the k-most-shortest-paths between two nodes in a weighted graph?

An answer to either one is OK, though I wonder if an answer to the second question can be done more efficiently than $k$ calls to an answer to the first question.

Asked By : Realz Slaw

Answered By : Juho

In the $k$ shortest path problem, we wish to find $k$ path connecting a given vertex pair with minimum total length. Eppstein [1] has an algorithm running in $O(m+n \log n + k)$ time to find the $k$ shortest paths (allowing cycles) between a pair of vertices in a digraph. With the techniques of the paper, one can also find all path shorter than some given threshold, within the same time bounds. There is a vast literature on the subject, the Eppstein paper includes many references and discussion.

If you disallow cycles, you might want to look at the algorithm of Hershberger et al. [2].

---

[1] Eppstein, David. "Finding the k shortest paths." SIAM Journal on computing 28.2 (1998): 652-673. [CiteSeerX]

[2] Hershberger, John, Matthew Maxel, and Subhash Suri. "Finding the k shortest simple paths: A new algorithm and its implementation." ACM Transactions on Algorithms (TALG) 3.4 (2007): 45. [CiteSeerX]

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18849