Is there an efficient algorithm for printing all edge-disjoint paths in a flow network?

Question

I was curious if there is an efficient algorithm for actually returning all edge-disjoint paths from s to t in a flow graph?

For example, take the following network where each edge has a capacity of 1:

It is clear that there are only two edge-disjoint paths:

1. s -> A -> B -> t
2. s -> C -> D -> E -> F -> t

I am guessing you need to use a modified version of the Ford-Fulkerson algorithm that keeps track of the augmented paths. But how does it override previous erroneous paths (like s -> A -> E -> F -> t in my example).

Answer 1

As you note, the augmenting paths used by Ford--Fulkerson are not immediately useful.

What you can do instead is run F--F (or any max flow algorithm) to completion and then greedily extract paths from the resulting flow. To extract a path, start at s. If there are no outgoing flow arcs left, then there are no paths left to extract. Otherwise, choose any flow arc whose tail is the current vertex, move to the head of that arc, delete that arc, repeat until the current vertex is t, print the sequence of arcs.

If you need simple paths, then you also need to detect when a path doubles back on itself and delete the cycle. This can be accomplished efficiently by mapping the vertices visited by the current so far to the index of their incoming arc in the path.

If you need short simple paths, you can swap out F--F for a min-cost flow algorithm and omit the cycle detection (a flow with a positive-cost cycle cannot be min-cost).