Looking for k shortest paths that do not share edges. i.e if the paths were represented as sets of edges, their intersection has to be empty.We could use Dijkstra to find the 1st disjoint (edge unique) shortest path from the origin to all vertices. However, to naively find the 2nd disjoint path, one would need to create $|V|$ versions of the graph, each one with a specific set of set of edges missing, corresponding to a path that was discovered with the original Dijkstra results.Is there a more computationally efficient method to find the $k$ shortest, edge disjoint paths? Even a heuristic would help me.Edit:I think this article posted by Raphael is exactly what I need to $k=2$ but I would like to support a great k if possible, up to 4. One more thing, I don't understand the following instruction:Replace each edge of the shortest path (equivalent to two oppositely directed arcs) by a single arc directed towards the source vertexWhat does equivalent to two oppositely directed arcs mean? What does replacing an edge with a single arc directed towards the source vertex mean?https://en.wikipedia.org/wiki/Edge_disjoint_shortest_pair_algorithmWait, the problem with the above algorithm is that it doesn't lessen the complexity. It is just as efficient as running Dijkstra twice for each pair of vertices. I'm looking for a better way to get the k disjoint shortest paths between each $v_i$ and $v_j$
Computing the k shortest edge-disjoint paths on a weighted graph
algorithms;graphs;shortest path;weighted graphs