Network Flow
How much can be pushed from a source to a sink through edges with capacities, and which edges are the bottleneck.
A flow network is a directed graph where every edge has a capacity. A flow puts an amount on each edge that never exceeds its capacity and that, at every vertex other than the source and the sink, brings in exactly as much as it sends out. Maximum flow asks for the largest total that can leave the source under those two rules.
Every algorithm here is the same loop: find any path from source to sink in the residual graph, push its smallest remaining capacity along it, update, repeat until no such path exists. The idea that makes it correct is the backward residual edge. Pushing f units from u to v also creates f units of capacity from v to u, so a later path can cancel part of an earlier decision, and the search never has to guess right the first time.
How the path is chosen sets the running time. Any path at all is Ford-Fulkerson, O(E * max flow), which counts augmenting paths rather than vertices and can be as slow as the flow value is large. Picking the fewest-edge path with BFS gives Edmonds-Karp at O(V * E^2), independent of the capacities. Dinic groups paths into phases by BFS level and reaches O(V^2 * E). When the loop ends, the vertices still reachable in the residual graph form one side of a minimum cut, and the saturated edges leaving that side add up to exactly the max flow.
After this you can
- Build a residual graph and say what the backward edge is there to undo
- Push an augmenting path and update capacity in both directions correctly
- Read a minimum cut straight off the final residual graph
- Model bipartite matching as a unit-capacity network with a source and a sink
- Choose Edmonds-Karp or Dinic and say what each bound does and does not depend on
BFS finds the shortest augmenting path 0 > 1 > 3 > 5, residual capacities 10, 5, 7. The bottleneck is 5.
In this order
- Maximum FlowThe most that can be sent from source to sink; grows by augmenting paths in the residual graph until none is left.
- Ford-FulkersonAny augmenting path will do; push its bottleneck, and undoing flow along a backward residual edge is allowed.
- Minimum CutThe vertices still reachable in the final residual graph are S; the saturated edges leaving S sum to the max flow.
- Edmonds-KarpFord-Fulkerson with BFS, so each path is shortest; O(V E^2) regardless of capacities.
- DinicBuild a level graph with BFS, then push blocking flows with DFS; O(V^2 E).
- Bipartite MatchingUnit-capacity network from a source through left and right to a sink; each augmenting path is an alternating path.
Where people go wrong
Leaving out the backward edge
Pushing flow without adding the matching residual capacity in the opposite direction turns the whole thing into greedy path picking. On any network where a first path has to be partly undone it returns a number that is too small, and nothing in the run looks wrong.
Ford-Fulkerson with large capacities
The bound counts augmenting paths. Two edges of capacity one million joined by an edge of capacity one can force a million rounds if the path choice keeps using the middle edge, and with irrational capacities the loop need not terminate at all. Choosing the path by BFS removes the dependence on capacity entirely.
Adding up the cut edges in both directions
A cut's capacity is the sum of the edges going from the source side to the sink side only. Edges crossing back the other way contribute nothing, and counting them gives a total larger than the max flow, which is the usual sign the max-flow min-cut check has been coded wrong.
Or a different category
Graph Traversal
Capacities are all one and the question is only whether a route exists, not how much fits through at once.
Shortest Path
Edges carry costs rather than capacities and you want one cheap route rather than total throughput.