0
$\begingroup$

This question already has an answer here:

Like let’s say you find the shortest path, but you want to find an alternate path as well. In order to do that, you have to ignore each edge in the shortest path one at a time, and then find the shortest path without using that respective edge. At that point you have a set of alternate paths, of which you want to select the one that is the shortest yet also different enough.

But I don’t know how to find the alternate paths while skipping edges. Could anyone please clear this up

$\endgroup$

marked as duplicate by D.W. algorithms Mar 17 '17 at 16:08

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

3
$\begingroup$

Check out Yen's Algorithm for finding the K-shortest paths using any shortest path algorithm. The link provided uses Dijkstra's algorithm as an example

$\endgroup$
0
$\begingroup$

I think you already answered yourself. You should remove an edge each time from your graph, that belongs to the original shortest path and rerun the Dijkstra for the new graph and original source and destination vertices. At the end of an iteration you should restore the previously deleted edge and remove the next one from the original path. Iterate till you reach the destination vertex.

I don't know what do you mean different enough. If you delete an edge from the original path then the new shortest path could be vary from almost identical to completely different path.

$\endgroup$

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