Graph  13. Network Flow
#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 FordFulkerson algorithm, there are multiple ways.
 Every augmenting path has a
bottleneck
, which is the smallest(capacity  flow)
on the path. In the above example, the bottleneck is edge (3, 0)
Augmenting the flow
means updating the flow values along the augmenting path. For forward edge, increasing the flow by the bottleneck value.
 For backward edge, also called
residual edge
, decreasing the flow by the bottleneck 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
 Example of residual graph
#13.2 FordFulkerson Algorithm
Algorithm
 Keep finding augmenting path, then augments the flow until no more augmenting path from s to t
 The sum of the bottlenecks 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 FordFulkerson 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, EdmondsKarp
is the famous one.
Python FordFulkerson 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 FordFulkerson with Edmonds Karp


#13.4 Capacity Scaling
capacity scaling is another technique to use heuristic to efficiently find augmenting path.
 Find the largest capacity in the flow graph, call it U
 Find the delta, which is the largest 2^x that’s less or equal to U
 Find augmenting path with capacity > than delta
 If no more augmenting path has capacity greater than delta, then delta /= 2
 Repeat until delta <= 0


#13.5 Dinic Algorithm
Another heuristic to efficiently find augmenting path. 太难了.