Contenus

Toggle## Ford-Fulkerson algorithm

In order to initialize the algorithm, it is possible to attribute any flow in the graph by following simple paths (from the source to the sink). In the following diagram, we have taken the path s-2-3-t for initialization.

It is possible to form a cut using the last gap 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 cut the graph into two subsets, and form the value of the cut.

If you want to increase the flow by changing the value, you will need to increase the maximum flow that can pass through these arcs.

## Step by step Ford-Fulkerson algorithm

The initial flow is 0. Here the residual graph G_{f} is a copy of graph G. We are looking for a path from s to t, for example s-2-5-t:

The minimum value of the path is 8. We add this flow of 8 to the path in the graph G.

As a reminder, the residual graph must show the inverse arcs (representing the flows). The residual graph of the new iteration is as follows:

Here we choose the path s-2-3-5-t, with 2 for the blocking flow. When we choose an inverse arc (thus representing a flow) the new flow in the graph G is reduced as shown by this new graph G.

Value of the flow = 10. Etc…

Flow value = 16

Choice of reverse arc (3,2):

Flow value = 18.

Flow value = 19.

There is no longer a path from s to t, we have found a maximum flow for this graph G.