Maximum Network Flow

Intuition:

• The goal is to discover the maximum amount of something we can push through a network system in which each path some limiting bottleneck. For example, Road systems, and water pipelines.

• Big O: O(E*maximum flow)

Algorithm

English

1. Initialize all flows to 0.

2. Note a possible path in the residual network between the furthest two nodes (the source, and the sink). That is, find the path that will give you the greatest flow.

3. Note the minimum in the path.

4. Push the minimum flow through the augmented path to the sink.

   • Update the paths:

     • Subtract from the edge by the minimum

     • Add a reverse flow of value minimum

     • Note that reverse flow + subtracted edge will always = original flow.

5. Once no other paths are possible to push in flow, the algorithm is complete.

6. The maximum flow will be the sum of each augmented path you pushed into the sink from the source.

On Paper

1. Choose and prioritize the augmented paths that provide the most network flow.

2. Initial G_flow and G_residual

3. Next augmentations:

   • G_r:

   • See b

4. G_f:

   • Follow through the augmented path you’ve set up. Then, based on G_r, note whether your augmented path will flow through the directed arrows of G_r.

   • If it does, add to the current edge

   • If it does not follow the G_r augmented path, subtract.