Difference between revisions of "Ford–Fulkerson method"

From PEGWiki
Jump to: navigation, search
(Created page with "The Ford–Fulkerson method is a technique for solving the maximum flow problem. The input is a flow network, <math>G_0 = (V, s, t, c)</math>. Then the algorithm proceeds...")
 
(No difference)

Latest revision as of 04:12, 9 September 2013

The Ford–Fulkerson method is a technique for solving the maximum flow problem. The input is a flow network, G_0 = (V, s, t, c). Then the algorithm proceeds as follows:

  1. Start with the empty flow, f_0(u, v) = 0 for all u, v \in V. The corresponding residual network is then equivalent to the original flow network, G_0 = (V, s, t, c).
  2. Find an augmenting path. Let c_m be the minimum residual capacity along the augmenting path. Push c_m units of flow along the path, adding to the flow f_i to give an augmented flow f_{i+1}. Corresponding to the augmented flow is a new residual network, G_{i+1}.
  3. Repeat step 2 with the new flow and new residual network until an augmenting path can no longer be found. The final flow f_n is a max flow.

Correctness[edit]

If the algorithm terminates, then no augmenting path remains. By the augmenting path theorem, the flow f_n obtained is maximal.

If the capacities are finite and integral, then the algorithm is guaranteed to terminate. It is not hard to see that an invariant of the algorithm is that the residual capacities are all integral after each augmenting step. Therefore c_m \geq 1 in each step, and the flow so far increases by at least one unit in each step. The algorithm must then terminate after no more than M steps, where M is the value of the max flow. A similar argument applies when all edge weights are rational.

On the other hand, the algorithm is not guaranteed to terminate when the edge weights are allowed to be irrational.

Complexity[edit]

In step 2, we have a choice in how to find the augmenting path. The overall running time of the algorithm depends on the heuristic used to choose the path. In the most common choice of heuristic, known as the Edmonds–Karp algorithm, we always choose the shortest augmenting path using breadth-first search. (Note that the capacities are not lengths; each edge has length 1!) It is easy to see that the running time of such an approach is O((E+V)M). Under a more sophisticated analysis, we can derive the bound O(VE^2), which is independent of the edge capacities.

Other heuristics are possible. We could for example use depth-first search to find an augmenting path, which also gives an O((E+V)M) algorithm. Another possibility is to use a modification of Dijkstra's algorithm to find an augmenting path of maximal value, i.e., that maximizes c_m. In this case we have the bound O((E + V \log V)M).

A more sophisticated approach, known as Dinic's algorithm, runs in O(V^2 E) time, which can be sped up to O(V E \log V) using link/cut trees.

Retrieved from "http://wcipeg.com/wiki/index.php?title=Ford–Fulkerson_method&oldid=1735"