Given a flow network $G=(V,E)$, source $s$ , sink $t$ and capacity function $c:E \to \mathbb{R}^+ \cup \{0\}$ ; as well an edge $e=(u,v) \in E$. I need to find an efficient algorithm which finds among all possible flows between $s$ and $t$ , a flow $f$ where $f(e)$ is the maximum flow possible on the edge $e$ for it.
I want to use Ford Fulkerson algorithm but instead of using BFSs one after the other and increase the flow, first use all the paths through $e$, and then after we don't find any, go on with any path available to $t$ from $s$, or something in this direction..
Edit: You can assume that the capacities are integers.
Thanks a lot!
Try this: let $e$ join $v$ to $w$, delete every edge that is neither in a path from source to $v$ nor in a path from $w$ to sink, and find a maximal flow in what's left of the network.
EDIT: Here's another way to achieve this. Reviewing the notation: the source is $s$, the sink is $t$, the edge $e$ joins $u$ to $v$. Make believe the sink is $u$, and find a maximal flow in the network; let its value be $a$. Now make believe the source is $v$, and the sink is $t$, and find a maximal flow; let its value be $b$. Then the maximal flow achievable in $e$ is the smallest of the numbers $a$, $b$, and the capacity of $e$. Moreover, you can easily adjust the flows you have found to a flow with that maximal amount going through $e$ and with the rest of the flow maximal subject to that restriction.