Indian Computing Olympiad

Training Material

Network flows

Note: Network flows are not part of the syllabus for IOI/IOITC.

Given a network of pipes with a given capacity and two nodes, source and sink, what is the maximum flow that can be passed from source to sink? 

                 7
          -->u ------------->v
         /    \            /   \
        / 7    \       10 /     \5
       /        \        /       \
  source         \----  /         -->sink
       \        10     X         /
        \ 5           / \       /7
         \    <------/   \-->  /
          -->w-------------->z
                   7
  1. For each edge e, flow(e) ≤ capacity(e)
  2. At each node, flow into the node is equal to the flow out of the node (conservation of flow).

In this case, the maximum flow is 12:

  • send 5 along source→u→v→sink
  • send 5 along source→w→z→sink.
  • send 2 along source→u→v→w→z→sink

Observe that the edges (u,v) and (z,sink) together disconnect the source from the sink. This is called a "cut set". Clearly, any flow that goes from source to sink must go through this cut set and cannot exceed the capacity of the cut, namely 14. There may be many cut sets --- for instance, (source,u), (source,w) is also a cut set, with capacity 12.

It is clear that the maximum flow in the graph cannot exceed the capacity of the minimum size cut in the graph.

Claim: The maximum flow from source to sink is equal to the capacity of the minimum size cut in the graph.

How do we compute the maximum flow?

Suppose we start with a flow 

          5     5     5           <--flow
  source---->o---->o---->sink
          5    10     5           <--capacity

Now, we select another path (ignoring directions) to augment the flow.

An augmenting path is a path from source to sink where

  • forward edges, flow < capacity
  • backward edges, flow > 0

e.g. we may have a path that looks like 

          4     6      3       2         <--flow
  source---->o----->o<-----o<------sink
          5     5      4       3         <--capacity

For each edge on this path, we compute leeway(e), defined as:

  • if e is a forward edge : capacity(e) - flow(e)
  • if e is a backward edge : flow(e)
          4     6      3       2         <--flow
  source---->o----->o<-----o<------sink
          5     7      4       3         <--capacity
          1     1      3       1         <--leeway

Augment flow upto min leeway along the path. Here min leeway is 1, so you can augment flow. On reverse edges, cancel out the existing flow, so reduce by the augmented amount.

After augmentation. 


          5     7      2       3         <--new flow
  source---->o----->o<-----o<------sink
          5     7      4       3         <--capacity

Repeat the augmentation step till you cannot find an augmenting path. (This algorithm is called the Ford-Fulkerson algorithm.)

Example: 

                    7
          -->u ------------->v
         /    \            /   \
        / 7    \       10 /     \5
       /        \        /       \
  source         \----  /         -->sink
       \        10     X         /
        \ 5           / \       /7
         \    <------/   \-->  /
          -->w-------------->z
                   7

Start with a flow 


            5     5     5         <--flow
   source ---->u---->z---->sink
            7    10     7         <--capacity

Find an augmenting path, for example: 

            5     0     0         <--flow
   source ---->u---->v---->sink
            7     7     5         <--capacity
            2     7     5         <--leeway

Add flow on this path 

            7     2     2         <--augmented flow
   source ---->u---->v---->sink
            7     7     5         <--capacity

Now, another augmenting path (with backward edges): 

            0     0     5     2     2       <--flow
   source ---->w---->z<----u---->v---->sink
            5     7     10    7     5       <--capacity
            5     7     5     5     3       <--leeway

Augmented flow 

            3     3     2     5     5       <--flow
   source ---->w---->z<----u---->v---->sink
            5     7     10    7     5       <--capacity

Finally, we have an augmenting path 

            3     3     5         <--flow
   source ---->w---->z---->sink
            5     7     7         <--capacity
            2     4     2         <--leeway

Augmented flow 

            5     5     7         <--augmented flow
   source ---->w---->z---->sink
            5     7     7         <--capacity

Add s→w→z→u→v→t

How do we find augmenting paths?

  • Use BFS. At each node:
    • take a forward edge if flow < capacity
    • take a backward edge if flow > 0
  • If you reach the sink, you have found an augmenting path.

In the worst case, you have to do one iteration for each unit of flow. Let F be the optimum flow. Then, we have F iterations, each of which requires finding an s-t path (BFS/DFS), so it takes mF time. (This assumes that flows are all integers).

Here is a worst case scenario: 

                                 10000      10000
                                     --->A---------->t
                                    /     \       -->
                                   /       \1    /
                                  s         --> / 9000
                                   ----------->B
                                           9000

Here, if we always choose a path that includes the edge AB (or BA), each step increases the max flow by exactly 1 unit, so it takes 19000 iterations to terminate. (Of course, we could have been lucky and chosen directly the upper and lower paths to augment.)

Claim: If we always augment the flow by finding the shortest s-t path in terms of number of edges, the algorithm terminates in time O(mn). (We will not prove this). Notice that if we search for augmenting paths via BFS, we are guaranteed to find the shortest augmenting path at each stage.

Observe: If the capacities are integers, each time we augment the flow, we augment it by an integer. So, the max flow will always be integral.

Video material

Video lecture on Network flows, NPTEL online course on Design and Analysis of Algorithms (Lecture slides)



Problems based on network flows

Basic topics

Advanced topics