Design and Analysis of Algorithms

302 Design and Analysis of Algorithms

Defi ne fl ow f

p

in G

f

as

f

p

(u, v) =

() if(,)on

() i

f(,)on

0otherwise

f

f

cp uv p

cp vu p

⎧

⎪

−

⎨

⎪

⎩

| f

p

| = c

f

(p) > 0

Defi ne fl ow sum f

1

+ f

2

as (f

1

+ f

2

)(u, v) = f

1

(u, v) + f

2

(u, v).

If the fl ow network G has fl ow f, an augmenting path p in G

f

, and f ′ = f + f

p

, then f ′ is a fl ow in G with

value | f ′| = | f | + | f

p

| > | f |.

So the basic idea in the algorithm is: keep adding augmenting paths until there are no more.

There is a theorem which states that:

f is a maximum fl ow in G if and only if the residual network G

f

has no augmenting paths.

The Ford-Fulkerson algorithm is given as Algorithm 11.19.

Algorithm 11.19