In order to initialize the algorithm, it is possible to assign any flow in the graph by following simple paths (from the source to the well). In the following diagram, we took for initialization the path s-2-3-t.
It is possible to form a cut using the last residual graph. We apply a path from s, all the vertices that can be traversed are in the set S, the others in the set T. Indeed, the arcs saturated by the flow intersect the graph in two subsets, and form the value of the cut.
If one wishes to increase the flow by a change of value, it will be necessary to increase the maximum flow which can pass by these arcs.
Step by step
The initial flow is equal to zero. The residual graph Gf is here a copy of the graph G. We have to find a path from s to t, for example s-2-5-t:
The minimal value on this path is 8. Thus, we have a flow equal to 8 on this path on the graph G.
Remind that the residual graph shows the flow as a reverse arc. Construct the residual graph from this iteration:
Here we choose the augmenting path s-2-3-5-t, with 2 as a bottleneck. If we choose a reverse arc, the flow through the arc is reduced (not in this case, but it can happen).
Flow Value = 10. So on…
Flow value = 16
At this point, we choose the reverse arc (3,2), see what happened in the graph G below.
No more path from s to t, we find a maximum flow on this graph.