1
$\begingroup$

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:

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?

$\endgroup$

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.