# Enumerating all edge-disjoint shortest paths from “s” to “t”

Given:

1. An edge-weighted directed graph $$G$$
2. A start vertex $$s$$
3. A target vertex $$t$$

I want to enumerate all edge-disjoint shortest paths from $$s$$ to $$t$$, in ascending order of path length.

So, as an example, given the following graph:

I want the algorithm to output the following paths in the following order:

1. A $$\rightarrow$$ B $$\rightarrow$$ C (length: 1+1)
2. A $$\rightarrow$$ C (length: 3)
3. A $$\rightarrow$$ B $$\rightarrow$$ C (length: 2+2)
4. A $$\rightarrow$$ C (length: 5)

The simplest algorithm I can imagine is as follows:

1. Apply shortest path-algorithm to $$G$$ (e.g. Dijkstra, or Bellman-Ford if $$G$$ has negative-weight edges) to find the shortest path from $$s$$ to $$t$$ (if no path exists then terminate)
2. Append this shortest path to the list of shortest paths
3. Remove all edges in this shortest path from the graph, to obtain a new graph, and apply step 1 to this new graph.

If we let $$p$$ denote the number of edge-disjoint shortest paths in $$G$$, then the complexity of this algorithm is simply $$p$$ times the complexity of whichever shortest path algorithm is chosen.

Is there a more efficient algorithm than this?