Introduction to Algorithms, Third Edition

The basic Ford-Fulkerson algorithm
In each iteration of the Ford-Fulkerson method, we find
some
augmenting path
p
and use
p
to modify the flow
f
. As Lemma 26.2 and Corollary 26.3 suggest, we
replace
f
by
f
"
f
p
, obtaining a new flow whose value is
j
f
j C j
f
p
j
. The follow-
ing implementation of the method computes the maximum flow in a flow network
G
D
.V; E/
by updating the flow attribute
.u; /:
f
for each edge
.u; /
2
E
.
1
If
.u; /
62
E
, we assume implicitly that
.u; /:
f
D
0
. We also assume that we
are given the capacities
c.u; /
along with the flow network, and
c.u; /
D
0
if
.u; /
62
E
. We compute the residual capacity
c
f
.u; /
in accordance with the
formula (26.2). The expression
c
f
.p/
in the code is just a temporary variable that
stores the residual capacity of the path
p
.
F
ORD
-F
ULKERSON
.G; s; t /
1
for
each edge
.u; /
2
G:
E
2
.u; /:
f
D
0
3
while
there exists a path
p
from
s
to
t
in the residual network
G
f
4
c
f
.p/
D
min
f
c
f
.u; /
W
.u; /
is in
p
g
5
for
each edge
.u; /
in
p
6
if
.u; /
2
E
7
.u; /:
f
D
.u; /:
f
C
c
f
.p/
8
else
.; u/:
f
D
.; u/:
f
c
f
.p/
1
Recall from Section 22.1 that we represent an attribute
f
for edge
.u; /
with the same style of
notation—
.u; /:
f
—that we use for an attribute of any other object.

---

26.2
The Ford-Fulkerson method
725
The F
ORD
-F
ULKERSON
algorithm simply expands on the F
ORD
-F
ULKERSON
-
M
ETHOD
pseudocode given earlier. Figure 26.6 shows the result of each iteration
in a sample run. Lines 1–2 initialize the flow
f
to
0
. The
while
loop of lines 3–8
repeatedly finds an augmenting path
p
in
G
f
and augments flow
f
along
p
by
the residual capacity
c
f
.p/
. Each residual edge in path
p
is either an edge in the
original network or the reversal of an edge in the original network. Lines 6–8
update the flow in each case appropriately, adding flow when the residual edge is
an original edge and subtracting it otherwise. When no augmenting paths exist, the
flow
f
is a maximum flow.