Page 284 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 14: Network Flows

the first path we found was s → b → a → t. If we push as much flow as possible, then we end up Notes
with the following:
Figure 14.2: We have Pushed 3 Flow along the Path s → b → a → t

a
3/4
0/2

s 3/3 t

3/4
0/2
b

Now we have run into a problem: our only options left are to push 1 unit of water along the path

s → a → t and 1 unit of water along s → b → t. After that, we won’t be able to find any more path

from s to t! Yet, we have only found 5 flow, which is not he maximum flow. Thus, the idea is not
optimal since it depends on how we picked our path. While we can try to find a ”good” path-

picking algorithm, it would be nice if the algorithm is not dependent on the paths we chose.
A crucial observation is that there is actually another path from s to t other than the two that we
mentioned above! Suppose we redirect 2 units of water from b → a → t to b → t, this will decrease
the amount of water running through the pipe (a; t) to 0. Now we have a path from s → a → t in
which we can flow 2 units of water! The graph now looks as follows:

Figure 14.3: The Bolded Edge indicate which Pipe has their Flow Adjusted

a
3/4
2/2

s 1/3 t

3/4
2/2
b

It is now easy to see that we can push 1 unit of water along s → b → a → t to obtain the maximum
flow of 6. If we carefully study in the Figure 14.3, what we have essentially done is to flow 2 unit

of water along s → a, and then push back 2 unit of water from a → b, and finally redirect the

pushed back flow along b → t to the sink. So the key to completing the algorithm is the idea of

pushing back flow - if we have x units of water flowing in the pipe (u; v), then we can pretend

there is a pipe (v; u) with capacity x when we are trying to find a path from s to t.
This is the concept of residual graph. The residual graph of a network flow is essentially the

network graph except that for every edge (u; v) that currently carries x unit of water, there is

LOVELY PROFESSIONAL UNIVERSITY 279