0
$\begingroup$

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$
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

| cite | improve this answer | |
$\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.

| cite | improve this answer | |
$\endgroup$

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