9
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ A Google search on "k shortest paths" turns up a number of references that describe algorithms for this problem. There's also a Wikipedia article on exactly this topic: en.wikipedia.org/wiki/K_shortest_path_routing $\endgroup$ – D.W. Dec 11 '13 at 1:10
  • $\begingroup$ @D.W. Make into an answer, with a short summary? $\endgroup$ – Raphael Feb 5 '15 at 11:14
5
$\begingroup$

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]

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.