26.2 The Ford-Fulkerson method

This section presents the Ford-Fulkerson method for solving the maximum-flow problem. We

call it a "method" rather than an "algorithm" because it encompasses several implementations

with differing running times. The Ford-Fulkerson method depends on three important ideas

that transcend the method and are relevant to many flow algorithms and problems: residual

networks, augmenting paths, and cuts. These ideas are essential to the important max-flow

min-cut theorem (Theorem 26.7), which characterizes the value of a maximum flow in terms

of cuts of the flow network. We end this section by presenting one specific implementation of

the Ford-Fulkerson method and analyzing its running time.

The Ford-Fulkerson method is iterative. We start with f(u, v) = 0 for all u, v V, giving an

initial flow of value 0. At each iteration, we increase the flow value by finding an

"augmenting path," which we can think of simply as a path from the source s to the sink t

along which we can send more flow, and then augmenting the flow along this path. We repeat

this process until no augmenting path can be found. The max-flow min-cut theorem will show

that upon termination, this process yields a maximum flow.

FORD-FULKERSON-METHOD(G, s, t)

1 initialize flow f to 0

2 while there exists an augmenting path p

3 do augment flow f along p

4 return f

The basic Ford-Fulkerson algorithm

In each iteration of the Ford-Fulkerson method, we find some augmenting path p and increase

the flow f on each edge of p by the residual capacity cf(p). The following implementation of

the method computes the maximum flow in a graph G = (V, E) by updating the flow f[u, v]

between each pair u, v of vertices that are connected by an edge.[1] If u and v are not

connected by an edge in either direction, we assume implicitly that f[u, v] = 0. The capacities

c(u, v) are assumed to be given along with the graph, and c(u, v) = 0 if (u, v) ∉ E. The

residual capacity cf(u, v) is computed in accordance with the formula (26.5). The expression

cf(p) in the code is actually just a temporary variable that stores the residual capacity of the

path p.

FORD-FULKERSON(G, s, t)

1 for each edge (u, v) E[G]

2 do f[u, v] © 0

3 f[v, u] © 0

4 while there exists a path p from s to t in the residual network Gf

5 do cf(p) © min {cf(u, v) : (u, v) is in p}

6 for each edge (u, v) in p

7 do f[u, v] © f[u, v] + cf(p)

8 f[v, u] © -f[u, v]