In a particular network G = (V, E) whose edges have integer capacities c_e, we have already found the maximum flow f from node to node t. However, we now find out that one of the capacity values we used was wrong: for edge (u, v) we used c_uv whereas it should have been c_uv. -1 This is unfortunate because the flow f uses that particular edge at full capacity: f = c.

We could redo the flow computation from scratch, but there’s a faster way. Show how a new optimal flow can be computed in$\mathit{O}\mathbf{(}\left|V\right|\mathbf{+}\left|E\right|\mathbf{)}$ time.

1. Let E' be the edges $e\in 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\in E{P}_1\cup \left\{\left(u,v\right)\right\}\cup 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\cup \left\{\left(u,v\right)\right\}\cup 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|)$.