Ford–Fulkerson algorithm

Fulkerson algorithm Ford and is a method in the field of computational graph theory for determining a maximum flow in a flow network. The algorithm, after its inventors, L.R. Ford Jr. and D. R. Fulkerson named. The termination of the algorithm is ensured if the flow network has rational capacities. However, the algorithm has a superpolynomial worst-case run-time. Further developments led to the Edmonds - Karp algorithm and the algorithm of Dinic.

The algorithm

Given a network consisting of a finite, directed graph with a source, a sink and a capacity function that assigns a non-negative real number to each edge as capacity.

The algorithm changed in each run an st- flow in the network, ie a mapping with the properties

• Capacity Constraint: For each edge of the river is limited by.
• Flow conservation: For each node: .

Herein, the amount of addition of the leading edges and the amount of the leading edge to enter. So the incoming flow into a node must be equal to the outgoing flow.

The algorithm searches a path from to in Residualgraphen in each step. The Residualgraph shares with the same vertex set and contains the edges of which are underutilized by, supplemented by so-called back edges: For each edge, each with an additional rear edge contains. Formally, the following applies: given Residualkapazitäten are defined that map each edge, to how much the flow can be increased to a still, and assign each back edge to how much the flow can be reduced to the corresponding Hinkante. So formally:

For initialization, any flow can be used (including the zero flow, which assigns each edge a value of 0 ). The algorithm describes itself as follows:

Are all rational capacities, the algorithm based on a finite number of steps a maximum st- flow.

Example

Initialize with the river.

Increase the flow along the path by 3, the result is, it stays.

Increase the flow along the path by one, this gives, and.

There arises.

The algorithm stops here, as in the remaining residual network no path from there for more. The river reached it can be seen by their number one takes every red edge as the size of the river on the upturned edge. The remaining black edges indicate the unused Residualkapazitäten.

For the correctness of the algorithm

Ford and Fulkerson proved that an st- flow in a network is exactly at a maximum when there is no augmenting path, ie if the residual network does not have a path from to. Therefore:

Here, the maximum st- flow need not be uniquely determined.

In implementing the algorithm, the observed flux increases with each step. It follows an important fact for integer networks:

If all capacities are rational numbers, we obtain by multiplying by the common denominator of an integral network, and can thus prove the following assertion:

If irrational numbers exist as capacity, is no longer true: Ford and Fulkerson constructed an example of a network with 10 nodes and 48 edges, in which their algorithm with a suitable choice of augmenting paths do not come to a halt and does not converge to a maximum flow. In 1995, Uri Zwick found an example with 6 nodes and 8 edges and such a behavior.

Term

On one hand, each time through the loop of the algorithm only requires time (see Landau notation), but on the other hand depends on the required number of loop iterations on the size of capacity from. It is possible to choose the paths flussvergrößernden very unfavorable.

Whatever one chooses in each step a shortest augmenting path to increase the flow, we obtain the algorithm of Edmonds and Karp, who always constructs a maximum st- flow in runtime. Another improvement with the help of additional techniques brings the algorithm of Dinic with a ( worst-case) complexity of.