> For the complete documentation index, see [llms.txt](https://maksimdan.gitbook.io/ecs122a-algorithm-design-lecture-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://maksimdan.gitbook.io/ecs122a-algorithm-design-lecture-notes/network_flow/maximum_network_flow.md).

# 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.