## #13. Network Flow

### #13.1 Concept

#### #What is a Flow Graph?

A flow graph is a `directed`, where each edge (also called an arc) has a certain capacity

#### #What is an Augmenting Path?

Augmenting path is a path of edges in the residual graph with remaining capacity greater than 0 from the source s to the destination t. • How to find the augmenting path is flexible in Ford-Fulkerson algorithm, there are multiple ways.
• Every augmenting path has a `bottle-neck`, which is the smallest `(capacity - flow)` on the path.
• In the above example, the bottle-neck is edge (3, 0)
• `Augmenting the flow` means updating the flow values along the augmenting path.
• For forward edge, increasing the flow by the bottle-neck value.
• For backward edge, also called `residual edge`, decreasing the flow by the bottle-neck value
• `Residual edge` exist to undo bad augmenting paths that do not lead to a maximum flow

#### #What is Residual Graph?

• Think every edge in the original graph as also having a residual edge with a flow/capacity of `0/0`
• The resulting graph is a residual graph
• Example of residual graph ### #13.2 Ford-Fulkerson Algorithm

Algorithm

• Keep finding augmenting path, then augments the flow until no more augmenting path from s to t
• The sum of the bottle-necks found in each augmenting path is equal to the max flow.
• The flow into the destination is also the max flow

Assuming the method of finding augmenting paths is by using DFS, then the Ford-Fulkerson algorithm runs in `O(fE)`, where f is the maximum flow and E is the number of Edges.

There are other ways to find the augmenting path, `Edmonds-Karp` is the famous one.

Python Ford-Fulkerson Algorithm

### #13.3 Edmonds Karp Algorithm

• Using BFS instead of DFS to find the augmenting path.
• Takes `O(VE^2 )` time, the difference is this time complexity no longer depends on the capacity value of any edge.

Python Ford-Fulkerson with Edmonds Karp

### #13.4 Capacity Scaling

capacity scaling is another technique to use heuristic to efficiently find augmenting path.

1. Find the largest capacity in the flow graph, call it U
2. Find the delta, which is the largest 2^x that’s less or equal to U
3. Find augmenting path with capacity > than delta
4. If no more augmenting path has capacity greater than delta, then delta /= 2
5. Repeat until delta <= 0

### #13.5 Dinic Algorithm

Another heuristic to efficiently find augmenting path. 太难了.