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.
$\endgroup$3 Answers
$\begingroup$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.
$\endgroup$ $\begingroup$This is a well known problem.
See , section 5.5.
$\endgroup$ $\begingroup$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.
$\endgroup$
