(thing) by ariels Tue Apr 06 2004 at 12:01:12

The Ford-Fulkerson algorithm is an algorithm for finding the maximum flow (which see!), and consequently constructing a maximal flow, in a capacitated graph.

Let G=(V,E) be directed graph, let s,t∈V be source and sink vertices, and let c:E→[0,∞) be capacities for the edges of G. We're seeking a maximal flow: a flow f:E→[0,&infin) of the maximal possible size

|f| = ∑{v: (s,v)∈E} f(s,v) - ∑{v: (v,s)∈E} f(v,s) = ∑{u: (u,t)∈E} f(u,t) - ∑{u: (t,u)∈E} f(t,u)
on (G,s,t,c).

The Ford-Fulkerson algorithm does the simplest thing possible. At each iteration it has some feasible flow f, which it attempts to improve. It searches for a undirected path from s to t which isn't saturated.

A path P=(v0,v1,...,vk) is saturated if for each i=1,...,k,
f(vi-1,vi) = c(vi-1,vi) if (vi-1,vi)∈E, or
f(vi,vi-1) = 0 if (vi,vi-1)∈E
Such a path can be easily found, using any of the path-seeking algorithms (e.g. Dijkstra's algorithm).

Suppose there is such an unsaturated path, then we can improve the flow f very easily. Define the slack of the edges along the path:

  • For each edge ei=(vi-1,vi)∈E, we can define di = c(vi-1,vi)-f(vi-1,vi) > 0;
  • For each edge ei=(vi,vi-1)∈E, we can define di = f(vi-1,vi) > 0.
Taking d = mini=1,...,k di, we see that we can augment the flow by d. Define a new flow f' by:
  • For each edge ei=(vi-1,vi)∈E, define 0 ≤ f'(ei) = f(ei) + d ≤ c(vi-1,vi).
  • For each edge ei=(vi,vi-1)∈E, define 0 ≤ f'(ei) = f(ei) - d ≤ c(vi-1,vi).
  • For every other edge e not in the path, define f'(e)=f(e).
Then f' is a flow, with |f'| = |f|+d > |f|.

So we have a procedure to increase any flow with an unsaturated path. The Ford-Fulkerson algorithm is simply:

  1. Initialise some flow (usually f=0).
  2. Find an unsaturated path for the flow f; if all paths are saturated, terminate.
  3. Otherwise: Increase flow f along the unsaturated path, and continue with step 2.

See a proof of the Ford-Fulkerson algorithm for and why if the algorithm terminates it finds a correct answer, and for why this algorithm does indeed terminate when all values are integers. Note that if all capacities are integers, and if we start with the flow f≡0, then all values in every flow appearing in the algorithm are also integers. Thus, we have that

If all capacities are integers, the size of the maximal flow is an integer, and there exists a maximal flow with integer flows along each edge.

Running time for the algorithm -- when all capacities are integers -- is O(n⋅m⋅c) -- the product of the number of vertices (giving a bound on the time to find an unsaturated path), the number of edges, and the maximal capacity of all edges. More efficient algorithms exist, but Ford-Fulkerson offers the nicest formulation.

We also have the following neat results which follow from the proof:

  • "max flow = min cut": The maximal flow -- that found by the algorithm -- has equal size to the size of the minimal cut in the graph.
  • Linear programming: Maximal flow is a linear programming problem (in particular, general algorithms for linear programming will solve it). Minimal cut is its dual problem, so the above is a special case of duality in linear programming.
  • Related NP-complete problems:
    1. max cut is NP-complete; evidently we were lucky with the structure of the "max flow" problem.
    2. Integer linear programming -- linear programming with all scalars limited to integer values -- is NP-complete; evidently we were extremely lucky with the structure of the "max flow" problem, which allows us to find integer solutions to a (particular type of) integer linear programming problem.

I like it!