# Finding the k-shortest path between two nodes

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.

• 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 – D.W. Dec 11 '13 at 1:10
• @D.W. Make into an answer, with a short summary? – Raphael Feb 5 '15 at 11:14

In the $k$ shortest path problem, we wish to find $k$ path connecting a given vertex pair with minimum total length. Eppstein  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.