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.
Finding the k-shortest path between two nodes
algorithms;graphs;shortest path;graph traversal
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]