5.1.2. The Edmonds-Karp Algorithm

The Edmonds-Karp algorithm is a variation of the Ford-Fulkerson algorithm that uses what can be considered a fairly natural greedy strategy for finding an augmenting path: Run BFS from \(s\) in \(G^f\) to find a shortest \(st\)-path \(P\) in \(G^f\). An example of running the Edmonds-Karp algorithm is shown in Figure 5.12.

Figure 5.12: Illustration of an application of the Edmonds-Karp algorithm to the network in Figure 5.1. The edge labels in the left column show the current flow. The right column shows the corresponding residual networks and a possible path in the residual network used to augment the flow. Edge labels are residual capacities. The last residual network contains no \(st\)-path, as illustrated by the shaded cut. The corresponding flow in the bottom-left figure is thus a maximum flow in \(G\).

Since the Edmonds-Karp algorithm is a variant of the Ford-Fulkerson algorithm, it returns a maximum \(st\)-flow if it terminates. The remainder of this section is focused on proving that it does, in \(O\bigl(nm^2\bigr)\) time. The proof makes use of the following lemma:

Lemma 5.5: Let \(f\) be some \(st\)-flow in \(G\), let \(P\) be a shortest path from \(s\) to \(t\) in \(G^f\), and let \(f'\) be the \(st\)-flow obtained by applying the Augment procedure to \(f\) and \(P\). Then \(\mathrm{dist}_{G^{f'}}(s,x) \ge \mathrm{dist}_{G^f}(s,x)\) for all \(x \in V\).

In other words, as the Edmonds-Karp algorithm sends flow along augmenting paths, the shortest paths from \(s\) to all vertices in the residual network \(G^f\) become longer and longer (or at least not shorter).

Proof: Assume for the sake of contradiction that there exists a vertex \(x\) such that \(\mathrm{dist}_{G^{f'}}(s,x) < \mathrm{dist}_{G^f}(s,x)\) and choose such a vertex \(x\) with minimum distance \(\mathrm{dist}_{G^{f'}}(s,x)\). Since distances are integral, \(\mathrm{dist}_{G^{f'}}(s,x) < \mathrm{dist}_{G^f}(s,x)\) implies that

\[\mathrm{dist}_{G^{f'}}(s,v) \le \mathrm{dist}_{G^f}(s,x) - 1.\]

Let \(\Pi_{G^{f'}}(s,x)\) be a shortest path from \(s\) to \(x\) in \(G^{f'}\). Since \(\mathrm{dist}_{G^{f'}}(s,s) = 0 = \mathrm{dist}_{G^f}(s,s)\), \(x \ne s\), that is, \(x\) has a predecessor \(y\) in \(\Pi_{G^{f'}}(s,x)\). This predecessor satisfies

\[\mathrm{dist}_{G^{f'}}(s,y) = \mathrm{dist}_{G^{f'}}(s,x) - 1.\]

Thus, by the choice of \(x\),

\[\mathrm{dist}_{G^f}(s,y) \le \mathrm{dist}_{G^{f'}}(s,y) = \mathrm{dist}_{G^{f'}}(s,x) - 1 \le \mathrm{dist}_{G^f}(s,x) - 2.\tag{5.3}\]

Since every edge \((w,z) \in P\) satisfies

\[\mathrm{dist}_{G^f}(s,z) = \mathrm{dist}_{G^f}(s,w) + 1,\]

this implies that \((x,y) \notin P\) and \((y,x) \notin P\). In particular, \(f'_{x,y} = f_{x,y}\) and \(f'_{y,x} = f_{y,x}\). Thus, since \((y,x) \in G^{f'}\), \((y,x)\) is also an edge in \(G^f\), a contradiction because this would imply that

\[\mathrm{dist}_{G^f}(s,x) \le \mathrm{dist}_{G^f}(s,y) + 1,\]

but we observed in (5.3) that

\[\mathrm{dist}_{G^f}(s,x) \ge \mathrm{dist}_{G^f}(s,y) + 2.\ \text{▨}\]

Theorem 5.6: The Edmonds-Karp algorithm computes a maximum flow in \(O\bigl(nm^2\bigr)\) time.

Proof: As already observed, the correctness of the Edmonds-Karp algorithm follows because it is a variant of the Ford-Fulkerson algorithm. Next, we analyze its running time.

Constructing \(G^f\), running BFS in \(G^f\), and applying the Augment procedure to the path \(P\) found by the BFS takes \(O(m)\) time. Thus, it suffices to show that the algorithm terminates after at most \(nm\) iterations.

Let \(f^{(0)}, \ldots, f^{(r)}\) be the sequence of flows constructed by the algorithm. For \(0 \le i < r\), let \(P^{(i)}\) be the augmenting path used to produce \(f^{(i+1)}\) from \(f^{(i)}\) and let \(\delta^{(i)} = F^{(i+1)}_s - F^{(i)}_s\) be the amount of flow sent along this path. An edge \((x,y) \in E^{f^{(i)}}\) is critical for the augmenting path \(P^{(i)}\) if \((x,y) \in P^{(i)}\) and \(u^{f^{(i)}}_{x,y} = \delta^{(i)}\). In other words, the edge \((x,y)\) is one of the edges that limit the amount of flow sent along \(P^{(i)}\) to be no more than \(\delta^{(i)}\). Let \(E' = \{(x, y), (y, x) \mid (x, y) \in E\}\) be the set of edges in \(G\) and their reversals. We have \(|E'| \le 2m\) and every residual network \(G^{f^{(i)}} = \bigl(V, E^{f^{(i)}}\bigr)\) satisfies \(E^{f^{(i)}} \subseteq E'\). Thus, it suffices to show that every edge in \(E'\) is critical for at most \(\frac{n}{2}\) paths. Since every augmenting path \(P^{(i)}\) has at least one critical edge, this implies that \(r \le nm\), that is, the algorithm runs for at most \(nm\) iterations.

Consider an edge \((x, y) \in E'\) and two indices \(i < j\) such that \((x,y)\) is critical for \(P^{(i)}\) and \(P^{(j)}\) but not for any path \(P^{(h)}\) with \(i < h < j\). Then

\[\delta^{(i)} = u^{f^{(i)}}_{x,y} = u_{x,y} - f^{(i)}_{x,y} + f^{(i)}_{y,x} \ge f^{(i)}_{y,x}.\]

Thus,

\[f^{(i+1)}_{y,x} = f^{(i)}_{y,x} - \min\Bigl(\delta^{(i)},f^{(i)}_{y,x}\Bigr) = 0\]

and

\[\begin{aligned} f^{(i+1)}_{x,y} &= f^{(i)}_{x,y} + \max\Bigl(0, \delta^{(i)} - f^{(i)}_{y,x}\Bigr)\\ &= f^{(i)}_{x,y} + u_{x,y} - f^{(i)}_{x,y} + f^{(i)}_{y,x} - f^{(i)}_{y,x}\\ &= u_{x,y}. \end{aligned}\]

Therefore, \((x,y) \notin G^{f^{(i+1)}}\). Since \((x,y) \in P^{(j)}\), it does belong to \(G^{f^{(j)}}\). Thus, there exists a minimum index \(k > i + 1\) such that \((x,y) \in G^{f^{(k)}}\). Since \((x,y) \in G^{f^{(k)}}\) and \((x,y) \notin G^{f^{(k-1)}}\), the augmentation of \(f^{(k-1)}\) to produce \(f^{(k)}\) must push some flow from \(y\) to \(x\), that is, \((y,x) \in P^{(k-1)}\).

By Lemma 5.5,

\[\mathrm{dist}_{G^{f^{(k-1)}}}(s,y) \ge \mathrm{dist}_{G^{f^{(i)}}}(s,y).\tag{5.4}\]

Since \((y,x) \in P^{(k-1)}\) and \(P^{(k-1)}\) is a shortest path from \(s\) to \(t\) in \(G^{f^{(k-1)}}\),

\[\mathrm{dist}_{G^{f^{(k-1)}}}(s,x) = \mathrm{dist}_{G^{f^{(k-1)}}}(s,y) + 1.\tag{5.5}\]

By Lemma 5.5 again,

\[\mathrm{dist}_{G^{f^{(j)}}}(s,x) \ge \mathrm{dist}_{G^{f^{(k-1)}}}(s,x).\tag{5.6}\]

Since \((x,y) \in P^{(j)}\) and \(P^{(j)}\) is a shortest path from \(s\) to \(t\) in \(G^{f^{(j)}}\),

\[\mathrm{dist}_{G^{f^{(j)}}}(s,y) = \mathrm{dist}_{G^{f^{(j)}}}(s,x) + 1.\tag{5.7}\]

The combination of (5.4)–(5.7) shows that

\[\mathrm{dist}_{G^{f^{(j)}}}(s,y) \ge \mathrm{dist}_{G^{f^{(i)}}}(s,y) + 2.\]

Since every vertex \(y\) reachable from \(s\) in \(G^{f^{(h)}}\) satisfies \(\mathrm{dist}_{G^{f^{(h)}}}(s,y) \le n\), for all \(0 \le h < r\), this implies that the edge \((x,y)\) is critical for at most \(\frac{n}{2}\) of the paths \(P^{(0)}, \ldots, P^{(r-1)}\). ▨