Page 283 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes There are a bunch of junctions (nodes in the graph) and a bunch of pipes (edges in the graph)

connecting the junction. The pipe will only allow water to flow one way (the graph is directed).
Each pipe has also has a capacity (the weight of the edge), representing the maximum amount of

water that can flow through the pipe. Finally, we pour an infinite amount of water into the source

vertex. The problem is to find the maximum flow of the graph - the maximum amount of water

that will flow to the sink. Below is an example of a network fl ow graph.
Figure 14.1: A Simple Network Flow Graph. There are currently no water fl owing
a
0/4
0/2

s 0/3 t

0/4 0/2

b

It is fairly easy to see that the maximum flow in the Figure 14.1 is 6. We can flow 2 units of
water from s → a → t, 2 units of water from s → b → a → t, and 2 units of water from s → b →

t. This gives a flow of 6 and since all incoming edge to the sink are saturated, this is indeed the
maximum fl ow.

Note In the example, not all pipe are saturated with water.

14.1.1 Ford Fulkerson Method

It was easy to see the solution in the above example, but how do we find the solution in general?
One idea is to keep finding path from s to t along pipes which still has some capacities remaining

and push as much flow from s to t as possible. We will then terminate once we can’t fi nd any

more path. This idea seem to work since it is exactly how we found the maximum flow in the

example. However, there is one problem - we cannot guarantee which path we’ll fi nd first. In fact,
if we picked the wrong path, the whole algorithm will go wrong. For example, what happens if

278 LOVELY PROFESSIONAL UNIVERSITY