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

ford-fulkerson algorithm maximum flow max flow problem minimum cut gap graph increasing flow

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: we add the flow of the increasing path to the existing flow if the corresponding arc in the original graph is in the same direction as that of the deviation graph, otherwise we subtract the flow. The algorithm stops when there is no longer an increasing path.

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.

maximum flow max flow problem minimum cut deviation graph increasing flow ford-fulkerson algorithm

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.