- An edge-weighted directed graph $G$
- A start vertex $s$
- 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:
- A $\rightarrow$ B $\rightarrow$ C (length: 1+1)
- A $\rightarrow$ C (length: 3)
- A $\rightarrow$ B $\rightarrow$ C (length: 2+2)
- A $\rightarrow$ C (length: 5)
The simplest algorithm I can imagine is as follows:
- 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)
- Append this shortest path to the list of shortest paths
- 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?