ayodhyya.comNetwork flow algorithms compute the maximum amount of flow that can be sent from a source to a sink in a capacitated directed graph. The Ford-Fulkerson method and its practical variant Edmonds-Karp are foundational.
The max flow min cut theorem states that the maximum flow equals the capacity of the minimum cut, connecting flow optimization to graph partitioning.
Ford-Fulkerson Method
Ford-Fulkerson repeatedly finds an augmenting path from source to sink using any traversal (DFS/BFS) and pushes flow along it. The algorithm terminates when no augmenting path exists in the residual graph.
Its time complexity depends on the maximum flow value F, giving O(E * F) in the worst case, which can be exponential with poor path selection.
int fordFulkerson(vector>& capacity, int s, int t) {
int V = capacity.size(), flow = 0;
vector> residual = capacity;
while (true) {
vector parent(V, -1);
stack st; st.push(s); parent[s] = s;
while (!st.empty() && parent[t] == -1) {
int u = st.top(); st.pop();
for (int v = 0; v < V; v++)
if (parent[v] == -1 && residual[u][v] > 0)
parent[v] = u, st.push(v);
}
if (parent[t] == -1) break;
int bottleneck = INT_MAX;
for (int v = t; v != s; v = parent[v])
bottleneck = min(bottleneck, residual[parent[v]][v]);
for (int v = t; v != s; v = parent[v]) {
residual[parent[v]][v] -= bottleneck;
residual[v][parent[v]] += bottleneck;
}
flow += bottleneck;
}
return flow;
} Edmonds-Karp Algorithm
Edmonds-Karp is Ford-Fulkerson with BFS-based path selection, ensuring the shortest augmenting path (in terms of number of edges) is used. This guarantees O(V * E²) time complexity.
BFS path selection prevents the exponential worst-case of DFS-based Ford-Fulkerson, making Edmonds-Karp practical for moderate-sized graphs.
int edmondsKarp(vector>& capacity, int s, int t) {
int V = capacity.size(), flow = 0;
vector> residual = capacity;
while (true) {
vector parent(V, -1);
queue q; q.push(s); parent[s] = s;
while (!q.empty() && parent[t] == -1) {
int u = q.front(); q.pop();
for (int v = 0; v < V; v++)
if (parent[v] == -1 && residual[u][v] > 0)
parent[v] = u, q.push(v);
}
if (parent[t] == -1) break;
int bottleneck = INT_MAX;
for (int v = t; v != s; v = parent[v])
bottleneck = min(bottleneck, residual[parent[v]][v]);
for (int v = t; v != s; v = parent[v]) {
residual[parent[v]][v] -= bottleneck;
residual[v][parent[v]] += bottleneck;
}
flow += bottleneck;
}
return flow;
} Frequently Asked Questions
What is the max flow min cut theorem?
It states that the maximum flow value from source to sink equals the total capacity of the minimum cut separating source from sink. This bridges network flow and graph cut problems.
When should I use Edmonds-Karp over Ford-Fulkerson?
Use Edmonds-Karp (BFS-based) when the graph may cause DFS to take exponential time, as BFS guarantees O(V*E²) worst-case complexity regardless of capacities.
Originally published on Ayodhyya. Last updated June 1, 2026.
Ford-Fulkerson and Edmonds-Karp
Ford-Fulkerson augments flow along any augmenting path and runs in O(E * max_flow). Edmonds-Karp uses BFS to find the shortest augmenting path each time, guaranteeing O(V E^2) regardless of capacities.
Dinic's Algorithm
Dinic's builds level graphs with BFS and pushes blocking flows with DFS, achieving O(V^2 E) — the fastest general max-flow algorithm in practice. It is the standard choice for competitive programming and production systems.
Real-World Applications
Network flow solves bipartite matching, image segmentation (min-cut), airline scheduling, bandwidth allocation, and supply-chain optimization. Max-flow min-cut duality connects it to linear programming.
Ford-Fulkerson and Edmonds-Karp
Ford-Fulkerson augments flow along any augmenting path and runs in O(E * max_flow). Edmonds-Karp uses BFS to find the shortest augmenting path each time, guaranteeing O(V E^2) regardless of capacities.<\/p>
Dinic's Algorithm
Dinic's builds level graphs with BFS and pushes blocking flows with DFS, achieving O(V^2 E) — the fastest general max-flow algorithm in practice. It is the standard choice for competitive programming and production systems.<\/p>
Real-World Applications
Network flow solves bipartite matching, image segmentation (min-cut), airline scheduling, bandwidth allocation, and supply-chain optimization. Max-flow min-cut duality connects it to linear programming.<\/p>