0
$\begingroup$

Given a graph $G=(V,E)$ and $2$ vertices $s,t \in V$, how can I find the maximum number of edge-disjoint paths from $s$ to $t$ using a flow network? $2$ paths are edge disjoint if they don't have any common edge, though they may share some common vertices.

Thank you.

3 Answers 3

2

Hint: if each edge has a capacity of one unit, different units of stuff flowing from $s$ to $t$ must go on edge-disjoint paths.

0

This is a well known problem.

See https://en.wikipedia.org/wiki/Maximum_flow_problem, section 5.5.

0

no. of edge disjoint paths=Max. flow in graph find augmenting path from source to sink by Edmond karp and that is the answer of edge disjoint path.