Question

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.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top