Monotonicity of Residual Distances & The $O(V E)$ Critical Edge Bound
Let $\delta_f(s, v)$ denote the unweighted shortest-path distance (number of edges) from $s$ to $v$ in the residual graph $G_f$. When we augment flow along a shortest path $P$, some forward edges saturate and disappear from $G_f$, while new reverse edges $(v, u)$ appear. Could a newly added reverse edge $(v, u)$ create a shortcut that decreases $\delta(s, w)$?
No! Because $P$ was a shortest path, $(u, v) \in P$ implies $\delta_f(s, v) = \delta_f(s, u) + 1$. Thus traversing $(v, u)$ backward goes from distance $d+1$ to distance $d$, which can never reduce the distance from $s$ to any vertex.
Lemma 1 (Distance Monotonicity): Under shortest-path augmentations, for every vertex $v \in V$, the residual distance $\delta_{f'}(s, v) \ge \delta_f(s, v)$ never decreases.
Lemma 2 (Critical Edge Saturation Bound): Call an edge $(u, v)$ critical during an augmentation if it is a bottleneck edge ($c_f(u, v) = \Delta$) that becomes saturated and disappears from $G_f$. How many times can $(u, v)$ become critical?
- When $(u, v)$ is critical, it lies on a shortest path: $\delta_f(s, v) = \delta_f(s, u) + 1$.
- Before $(u, v)$ can be used again, flow must be pushed along the reverse edge $(v, u)$ at some later flow $f'$, when $\delta_{f'}(s, u) = \delta_{f'}(s, v) + 1$.
- Combining with Lemma 1 ($\delta_{f'}(s, v) \ge \delta_f(s, v)$): $$\delta_{f'}(s, u) = \delta_{f'}(s, v) + 1 \ge \delta_f(s, v) + 1 = \delta_f(s, u) + 2$$
Every time $(u, v)$ re-enters $G_f$ and becomes critical again, $\delta(s, u)$ increases by at least $2$. Since $0 \le \delta(s, u) \le V - 1$, each of the $2E$ directed arcs is critical at most $V / 2$ times! Thus there are $O(V E)$ augmentations, each taking $O(E)$ BFS time, for $O(V E^2)$ total time. $\blacksquare$
Visualize Dinic’s BFS level graph L_G and current-arc DFS blocking flows alongside backward residual arcs (v→u), extract the saturated S-T minimum cut, or step through Hopcroft-Karp disjoint shortest augmenting paths.
Invariant & State
Notice that Edmonds-Karp runs a fresh $O(E)$ BFS from scratch for every single augmenting path. If there are $500$ parallel paths of length $k$, Edmonds-Karp rebuilds the exact same BFS tree $500$ times! This observation directly motivates Dinic's algorithm (next unit), which builds the BFS level graph once per distance level and saturates all paths of length $k$ in a single blocking-flow pass.
| Metric | Bound | Explanation |
|---|---|---|
| Total Augmentations | $O(V E)$ | Each of $2E$ residual edges saturates at most $V/2$ times |
| Cost per Augmentation | $O(E)$ | Unweighted BFS over residual graph $G_f$ |
| Worst-Case Time | $O(V E^2)$ | Strongly polynomial; independent of maximum capacity $U$ |
| Auxiliary Space | $O(V + E)$ | Residual adjacency list + parentEdge[V] BFS array |
Production C++20 Implementation: Edmonds-Karp with Predecessor Arc Recording
#include <vector>
#include <queue>
#include <algorithm>
#include <limits>
class EdmondsKarp {
public:
struct Arc {
int from, to;
long long cap;
};
explicit EdmondsKarp(int n) : numVertices(n), adj(n) {}
void addEdge(int u, int v, long long cap) {
adj[u].push_back(static_cast<int>(arcs.size()));
arcs.push_back({u, v, cap});
adj[v].push_back(static_cast<int>(arcs.size()));
arcs.push_back({v, u, 0});
}
long long maxFlow(int s, int t) {
long long flow = 0;
std::vector<int> parentArc(numVertices, -1);
while (bfs(s, t, parentArc)) {
long long bottleneck = std::numeric_limits<long long>::max();
for (int cur = t; cur != s; ) {
int id = parentArc[cur];
bottleneck = std::min(bottleneck, arcs[id].cap);
cur = arcs[id].from;
}
for (int cur = t; cur != s; ) {
int id = parentArc[cur];
arcs[id].cap -= bottleneck;
arcs[id ^ 1].cap += bottleneck;
cur = arcs[id].from;
}
flow += bottleneck;
}
return flow;
}
private:
int numVertices;
std::vector<Arc> arcs;
std::vector<std::vector<int>> adj;
bool bfs(int s, int t, std::vector<int>& parentArc) const {
std::fill(parentArc.begin(), parentArc.end(), -1);
parentArc[s] = -2; // Sentinel for source
std::queue<int> q;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int id : adj[u]) {
int v = arcs[id].to;
if (parentArc[v] == -1 && arcs[id].cap > 0) {
parentArc[v] = id;
if (v == t) return true;
q.push(v);
}
}
}
return false;
}
};parentVertex[v] = u Instead of parentArc[v] = idIn multigraphs (or networks where both $(u, v)$ and $(v, u)$ exist as original edges), there may be multiple parallel residual arcs between $u$ and $v$. Storing only the parent vertex u forces a linear scan of adj[u] during augmentation to locate the unsaturated arc. Always record the exact arc index parentArc[v] = id during BFS.