Ford-Fulkerson Algorithm

Contents

The Ford-Fulkerson algorithm searches for an increasing path in the graph residual. It saturates this path if it exists, otherwise it returns the maximum flow. More precisely, the algorithm establishes a minimal cut to verify the optimality criterion. Remember that the flow is less than or equal to the cut.

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 took for initialization the path s-2-3-t.

After construction of the residual graph, a path from s to t is chosen if there is one. Otherwise we have the maximum flow. In the first case, the new flow is calculated according to the increasing path chosen in the deviation graph: the flow of the increasing path is added to the existing flow if the corresponding arc in the original graph is in the same direction as that from the gap graph, otherwise the flow is subtracted. The algorithm stops when there is no longer an increasing path.

It is possible to form a cut using the last deviation graph. We apply a traversal 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 flows cut the graph into 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 through these arcs.

The Ford-Fulkerson algorithm step by step

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.

Flow value = 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.