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]