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 Fundamentals
Every flow algorithm rests on the same vocabulary, and these are the terms you'll lean on throughout. Capacity and conservation constraints define what a valid flow is; the residual graph and augmenting paths define how you improve one; and the s-t cut sets up the duality that the rest of the cheat sheet exploits. Get comfortable here before reaching for any specific algorithm.
| 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 |