The Ford-Fulkerson algorithm seeks a increasing path in the residual graph. It saturates this path if it exists, otherwise it returns the maximum flow. Specifically, the algorithm establishes a minimal cut to check the optimality criterion. It is recalled that the flow is less than or equal to the cut.

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.

After construction of the residual graph, a path from s to t is chosen if it exists. Otherwise we have the maximum flow. In the first case, the new flow is calculated according to the increasing path in the residual 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, 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 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.

Publicités