Introduction to Algorithms, Third Edition

Figure 26.7
(a)
A flow network for which F
ORD
-F
ULKERSON
can take
‚.E
j
f
j
/
time,
where
f
is a maximum flow, shown here with
j
f
j D
2,000,000. The shaded path is an aug-
menting path with residual capacity
1
.
(b)
The resulting residual network, with another augmenting
path whose residual capacity is
1
.
(c)
The resulting residual network.
Proof
We will suppose that for some vertex
2
V
f
s; t
g
, there is a flow aug-
mentation that causes the shortest-path distance from
s
to
to decrease, and then
we will derive a contradiction. Let
f
be the flow just before the first augmentation
that decreases some shortest-path distance, and let
f
0
be the flow just afterward.
Let
be the vertex with the minimum
ı
f
0
.s; /
whose distance was decreased by
the augmentation, so that
ı
f
0
.s; / < ı
f
.s; /
. Let
p
D
s
;
u
!
be a shortest
path from
s
to
in
G
f
0
, so that
.u; /
2
E
f
0
and
ı
f
0
.s; u/
D
ı
f
0
.s; /
1 :
(26.12)
Because of how we chose
, we know that the distance of vertex
u
from the source
s
did not decrease, i.e.,
ı
f
0
.s; u/
ı
f
.s; u/ :
(26.13)
We claim that
.u; /
62
E
f
. Why? If we had
.u; /
2
E
f
, then we would also have
ı
f
.s; /
ı
f
.s; u/
C
1
(by Lemma 24.10, the triangle inequality)
ı
f
0
.s; u/
C
1
(by inequality (26.13))
D
ı
f
0
.s; /
(by equation (26.12)) ,
which contradicts our assumption that
ı
f
0
.s; / < ı
f
.s; /
.
How can we have
.u; /
62
E
f
and
.u; /
2
E
f
0
? The augmentation must
have increased the flow from
to
u
. The Edmonds-Karp algorithm always aug-
ments flow along shortest paths, and therefore the shortest path from
s
to
u
in
G
f
has
.; u/
as its last edge. Therefore,
ı
f
.s; /
D
ı
f
.s; u/
1
ı
f
0
.s; u/
1
(by inequality (26.13))
D
ı
f
0
.s; /
2
(by equation (26.12)) ,

---

26.2
The Ford-Fulkerson method
729
which contradicts our assumption that
ı
f
0
.s; / < ı
f
.s; /
. We conclude that our
assumption that such a vertex
exists is incorrect.
The next theorem bounds the number of iterations of the Edmonds-Karp algo-
rithm.
Theorem 26.8
If the Edmonds-Karp algorithm is run on a flow network
G
D
.V; E/
with source
s
and sink
t
, then the total number of flow augmentations performed by the algorithm
is
O.VE/
.