# How does one implement Dijkstra while skipping an edge [duplicate]

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

• What do you mean be "alternate path"? – Yuval Filmus Mar 17 '17 at 10:55

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

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.