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:

enter image description here

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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.