Ford Fulkerson algorithm

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.

flow2

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.

cut3.png

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

ford1

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:

ford2

The minimal value on this path is 8. Thus, we have a flow equal to 8 on this path on the graph G.

ford3

Remind that the residual graph shows the flow as a reverse arc. Construct the residual graph from this iteration:

ford4

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).

ford5

Flow Value = 10. So on…

ford6ford7

Flow value = 16

ford8

At this point, we choose the reverse arc (3,2), see what happened in the graph G below.

ford9

Flow value=18.

ford10ford11

Flow Value=19.

ford12

No more path from s to t, we find a maximum flow on this graph.

 

Publicités