Network flow algorithms solve optimization problems on directed graphs where edges have capacities and we route flow from a source to a sink. They underpin matching, scheduling, routing, and combinatorial optimization across computer science, operations research, and competitive programming.
What This Cheat Sheet Covers
This topic spans 12 focused tables and 142 indexed concepts. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.
Table 1: Flow Network FundamentalsTable 2: Max-Flow Min-Cut TheoremTable 3: Ford-Fulkerson MethodTable 4: Edmonds-Karp AlgorithmTable 5: Dinic's AlgorithmTable 6: Push-Relabel FrameworkTable 7: Push-Relabel Variants and HeuristicsTable 8: Minimum-Cost FlowTable 9: Bipartite MatchingTable 10: Flow Decomposition and ExtensionsTable 11: Algorithm Complexity ComparisonTable 12: Implementation Patterns
Table 1: Flow Network Fundamentals
| Concept | Example | Description |
|---|---|---|
G=(V,E), s,t∈V, cap:E→ℝ≥0 | Directed graph with source s, sink t, non-negative edge capacities | |
f(u,v) ∈ [0, cap(u,v)] | Assignment satisfying capacity and conservation constraints | |
0 ≤ f(u,v) ≤ cap(u,v) | Flow on each edge cannot exceed its capacity | |
∑f(u,v) = ∑f(v,w) ∀v≠s,t | Flow in equals flow out at every internal vertex | |
|f| = ∑f(s,v) | Total flow leaving source (or entering sink) | |
Gf: cf(u,v)=cap(u,v)-f(u,v) | Graph of remaining capacities; adds backward edge with capacity f(u,v) | |
cf(u,v) = cap(u,v) - f(u,v) | Remaining capacity on forward edge; f(u,v) on backward edge | |
s→a→b→t in Gf | Path from s to t in residual graph with all positive residual capacities |