Introduction to Algorithms, Third Edition

Figure 26.6
The execution of the basic Ford-Fulkerson algorithm.
(a)–(e)
Successive iterations of
the
while
loop. The left side of each part shows the residual network
G
f
from line 3 with a shaded
augmenting path
p
. The right side of each part shows the new flow
f
that results from augmenting
f
by
f
p
. The residual network in (a) is the input network
G
.
When the capacities are integral and the optimal flow value
j
f
j
is small, the
running time of the Ford-Fulkerson algorithm is good. Figure 26.7(a) shows an ex-
ample of what can happen on a simple flow network for which
j
f
j
is large. A max-
imum flow in this network has value 2,000,000: 1,000,000 units of flow traverse
the path
s
!
u
!
t
, and another 1,000,000 units traverse the path
s
!
!
t
. If
the first augmenting path found by F
ORD
-F
ULKERSON
is
s
!
u
!
!
t
, shown
in Figure 26.7(a), the flow has value
1
after the first iteration. The resulting resid-
ual network appears in Figure 26.7(b). If the second iteration finds the augment-
ing path
s
!
!
u
!
t
, as shown in Figure 26.7(b), the flow then has value
2
.
Figure 26.7(c) shows the resulting residual network. We can continue, choosing
the augmenting path
s
!
u
!
!
t
in the odd-numbered iterations and the aug-
menting path
s
!
!
u
!
t
in the even-numbered iterations. We would perform
a total of 2,000,000 augmentations, increasing the flow value by only
1
unit in each.

---

26.2
The Ford-Fulkerson method
727
4
12
11
2
11
2
8
8
9
4
4
9
8
4
4
9
8
s
t
12
7
4
4
v
1
s
t
8/16
8/12
15/20
7/7
9
11/13
11/14
4/4
v
1
10
19
s
t
12
1
7
11
4
3
v
2
v
3
v
3
v
3
v
4
v
4
v
4
(d)
(f)
4
9
8
4
4
15
s
t
5
7
11
4
v
1
s
t
12/16
12/12
19/20
7/7
9
11/13
11/14
4/4
v
1
3
v
2
v
3
v
3
v
4
v
4
(e)
4
v
2
v
2
v
1
v
2
8
8