91Ó°ÊÓ

1. Let E' be the edges $e∈E$ which F(e) > 0, and let G' = (V,E'). Find in G' a path P₁ from s to u and a path P₂ from v to t.
2. [Special case: If P₁ from P₂ have some edge in common, then role="math" localid="1659793051037" $e∈E{P}_1∪\left\{\left(u,v\right)\right\}∪P_2$has a directed cycle containing (u,v). In this case, the flow along this cycle can be reduced by one unit without changing the size of the overall flow. Return the resulting flow.]
3. Reduce flow by one unit along $P_1∪\left\{\left(u,v\right)\right\}∪P_2$.
4. Run Ford-Fulkerson with this starting flow.
5. Flow start base on reduce unit and changing size of overall flow.

This source circulation had size F, as evidenced by the explanation and running time. Let's overlook the unique circumstance (2).

We have a valid flow that fulfils the new capacity limit and has size F - 1 during step (3) of the procedure. Its ideal flow underneath the new capacity limit is then determined by step (4), Ford-Fulkerson.

Therefore, the stream is at most F, Ford-Fulkerson only runs for one iteration. Because each step is shorter, the overall running time is linear $O(\left|\mathrm{V}\right|+\left|\mathrm{E}\right|)$.