Network Flow and Maximum Flow
Maximum flow repeatedly augments an s-to-t path in the residual graph, whose reverse edges preserve the ability to undo earlier routing decisions.
Flow constraints and the objective
A directed edge carries flow between zero and its capacity. Every nonterminal vertex obeys conservation: incoming flow equals outgoing flow. The value is net flow leaving the source, equivalently entering the sink. These constraints distinguish flow from ordinary path selection because many routes can carry fractions of the total simultaneously.
Capacities model bandwidth, assignments, matching, scheduling, and disjoint paths. Multiple sources or sinks can be reduced to one super-source and super-sink. Vertex capacities are represented by splitting a vertex into in/out copies joined by a capacity edge.
- Capacity bounds every edge
- Intermediate vertices conserve flow
- Super-nodes reduce multiple terminals
Residual graphs are the mechanism
For an original edge u→v, residual capacity c−f permits more forward flow. A reverse residual edge v→u with capacity f permits canceling previously sent flow. Omitting reverse edges turns a locally poor augmenting choice into a permanent mistake and breaks Ford–Fulkerson correctness.
An augmenting path uses only positive residual edges. Its bottleneck is the minimum residual capacity on that path. Subtract the bottleneck on forward residual edges and add it on reverse edges; the update preserves capacity and conservation while increasing total flow by exactly the bottleneck.
- Forward residual means unused capacity
- Reverse residual means cancellable flow
- The bottleneck limits augmentation
Terms, operations, and practical uses
Flow model
- CapacityCapacity is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
- Flow conservationFlow conservation is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
- Flow valueFlow value is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Residual graph
- Forward residualForward residual is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
- Reverse residualReverse residual is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
- Augmenting pathAugmenting path is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Optimality
- BottleneckBottleneck is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
- Minimum cutMinimum cut is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
- Max-flow min-cut theoremMax-flow min-cut theorem is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Edmonds–Karp augments residual paths
from collections import deque
c=[[0,3,2,0],[0,0,1,2],[0,0,0,3],[0,0,0,0]];n=4;s=0;t=3;flow=0
while True:
p=[-1]*n;p[s]=s;q=deque([s])
while q and p[t]<0:
u=q.popleft()
for v in range(n):
if p[v]<0 and c[u][v]>0:p[v]=u;q.append(v)
if p[t]<0:break
add=10**9;v=t
while v!=s:add=min(add,c[p[v]][v]);v=p[v]
v=t
while v!=s:u=p[v];c[u][v]-=add;c[v][u]+=add;v=u
flow+=add
print("Max flow:",flow)#include <algorithm>
#include <array>
#include <cstring>
#include <functional>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
int main() {
vector<vector<int>> c={{0,3,2,0},{0,0,1,2},{0,0,0,3},{0,0,0,0}};
int flow=0;
while(true) {
vector<int> p(4,-1);
queue<int> q;
p[0]=0;
q.push(0);
while(!q.empty()&&p[3]<0) {
int u=q.front();
q.pop();
for(int v=0;v<4;v++) if(p[v]<0&&c[u][v]>0) p[v]=u,q.push(v);
}
if(p[3]<0) break;
int add=1e9;
for(int v=3;v;v=p[v]) add=min(add,c[p[v]][v]);
for(int v=3;v;v=p[v]) {
int u=p[v];
c[u][v]-=add;
c[v][u]+=add;
}
flow+=add;
}
cout << "Max flow: " << flow << '\n';
}import java.util.*;
class Main {
public static void main(String[] args) {
int[][] c={{0,3,2,0},{0,0,1,2},{0,0,0,3},{0,0,0,0}};
int flow=0;
while(true) {
int[] p={-1,-1,-1,-1};
p[0]=0;
ArrayDeque<Integer> q=new ArrayDeque<>();
q.add(0);
while(!q.isEmpty()&&p[3]<0) {
int u=q.remove();
for(int v=0;v<4;v++) if(p[v]<0&&c[u][v]>0) {
p[v]=u;
q.add(v);
}
}
if(p[3]<0) break;
int add=Integer.MAX_VALUE;
for(int v=3;v!=0;v=p[v]) add=Math.min(add,c[p[v]][v]);
for(int v=3;v!=0;v=p[v]) {
int u=p[v];
c[u][v]-=add;
c[v][u]+=add;
}
flow+=add;
}
System.out.println("Max flow: "+flow);
}
}Step through it
Running on S→A 3, S→B 2, A→T 2, B→T 3, A→B 1
Ford–Fulkerson and Edmonds–Karp
Ford–Fulkerson is a method because it does not specify how to choose an augmenting path. With integer capacities, any path strategy terminates and a basic bound is O(E·F), where F is the maximum-flow value. Irrational capacities can produce nontermination under unfortunate choices.
Edmonds–Karp selects a shortest-edge-count augmenting path with BFS. Distances in the residual graph increase in a controlled way, yielding O(VE²) time independent of flow magnitude. It is slower than Dinic on large instances but ideal for a transparent interview implementation.
- Ford–Fulkerson leaves path choice open
- BFS defines Edmonds–Karp
- Integer capacities give integral augmentations
Why termination proves optimality
When no residual s-to-t path exists, let S be the vertices still reachable from s. Every original edge from S to V−S is saturated and every edge entering S carries zero net contribution across the cut. Therefore the current flow value equals that cut capacity.
Any feasible flow is at most every s-t cut capacity, so equality supplies both an upper bound and a matching construction. This is the max-flow min-cut theorem and the real correctness certificate—not simply the fact that the search loop stopped.
- Residual reachability defines the cut
- The final flow saturates its cut
- Flow value equals minimum-cut capacity
Implementation and testing
Store paired residual edges so an update can locate its reverse in O(1). BFS records both parent vertex and edge index, then the sink-to-source parent chain yields the bottleneck and update path. Parallel edges must remain distinct or have capacities summed deliberately.
Test zero-capacity edges, no source-sink path, parallel and antiparallel edges, a case that needs a reverse residual edge, source equal to sink under the chosen API, and capacities near integer limits. Use a wide type for total flow and capacity addition.
- Pair each edge with its reverse index
- Parents reconstruct the augmenting path
- Wide integers protect accumulated flow
Modeling before running flow
Each unit of the model must match the capacity meaning: people, jobs, bandwidth, or edges. For bipartite matching, source-to-left and right-to-sink capacities are one, so integrality turns flow units into selected pairs. Lower bounds, costs, and undirected capacities require transformations beyond basic max flow.
After computing, expose the reachable residual set as a certificate and verify total flow leaving s equals total entering t. Conservation assertions at every intermediate vertex catch reverse-edge and indexing bugs immediately. The numerical answer alone can coincide with the optimum even when individual edge flows are illegal.
- Capacities encode the real constraint
- Residual reachability certifies the answer
- Assert conservation, not only total value