Skip to content

5.6 The Edmonds–Karp algorithm

Part 3 · Flows · Chapter 5 · Chapter 5: Maximum flow · Lecture notes, volume 3 (PDF) · Exercises: Maximum flow · App: Maximum flow: Ford–Fulkerson and Edmonds–Karp

Definition 5.12: Edmonds–Karp algorithm

The Edmonds–Karp algorithm is the Ford–Fulkerson algorithm in which Step 1 uses the breadth-first search: \(\mathit{LIST}\) is a queue, the residual arcs leaving each node are scanned by increasing index of the head, and the search stops as soon as \(t\) is labelled. The capacities are any non-negative real numbers.

  • By Chapter 1, Proposition «BFS finds shortest paths in number of arcs», the augmenting path has the minimum number of arcs among the paths from \(s\) to \(t\) in \(G(\vet{x})\).

  • For a feasible flow \(\vet{x}\) and a node \(i\), \(d_{\vet{x}}(i)\) is the minimum number of arcs of a path from \(s\) to \(i\) in \(G(\vet{x})\), and \(d_{\vet{x}}(i)=+\infty\) if \(i\) is not reachable.

  • An arc of the augmenting path is critical if its residual capacity equals \(\delta\): after the augmentation its residual capacity is zero, and it leaves the residual network.

  • An augmentation along \(P\) lowers \(r_{ij}\) by \(\delta\) and raises \(r_{ji}\) by \(\delta\) on every arc \((i,j)\) of \(P\), and changes no other residual capacity. Hence the arcs that enter the residual network are reverses of arcs of \(P\).

Lemma 5.13: the distances do not decrease

Let \(\vet{x}'\) be obtained from \(\vet{x}\) by an augmentation along a path \(P\) from \(s\) to \(t\) of \(G(\vet{x})\) with the minimum number of arcs. Then \(d_{\vet{x}'}(i) \ge d_{\vet{x}}(i)\) for every \(i \in N\).

Proof

We show that every arc \((a,b)\) of \(G(\vet{x}')\) satisfies \(d_{\vet{x}}(b) \le d_{\vet{x}}(a)+1\).

  1. If \((a,b)\) is an arc of \(G(\vet{x})\), a shortest path from \(s\) to \(a\) followed by \((a,b)\) reaches \(b\) with \(d_{\vet{x}}(a)+1\) arcs.

  2. Otherwise \((a,b)\) is the reverse of an arc \((b,a)\) of \(P\). The part of \(P\) from \(s\) to each of its nodes has the minimum number of arcs: a path to that node with fewer arcs, followed by the rest of \(P\), would give a walk from \(s\) to \(t\) with fewer arcs than \(P\), and a path inside it (Chapter 1, Lemma «a walk contains a path»). Hence \(d_{\vet{x}}(a)=d_{\vet{x}}(b)+1\), and \(d_{\vet{x}}(b) \le d_{\vet{x}}(a)+1\).

Now let \(s=i_0,i_1,\dots,i_q=i\) be a path of \(G(\vet{x}')\) with \(q=d_{\vet{x}'}(i)\) arcs. Along its arcs \(d_{\vet{x}}\) grows by at most \(1\) at a time, so \(d_{\vet{x}}(i) \le d_{\vet{x}}(s)+q=d_{\vet{x}'}(i)\). If \(i\) is not reachable in \(G(\vet{x}')\), then \(d_{\vet{x}'}(i)=+\infty\). □

Lemma 5.14: critical arcs

In the Edmonds–Karp algorithm, let the residual arc \((i,j)\) be critical in the augmentation at the flow \(\vet{x}\), and critical again in a later augmentation at the flow \(\vet{y}\). Then \(d_{\vet{y}}(i) \ge d_{\vet{x}}(i)+2\).

Proof

We apply Lemma 5.13 at every augmentation between \(\vet{x}\) and \(\vet{y}\).

  1. At \(\vet{x}\), the arc \((i,j)\) lies on a path with the minimum number of arcs, so \(d_{\vet{x}}(j)=d_{\vet{x}}(i)+1\); after the augmentation \(r_{ij}=0\).

  2. At \(\vet{y}\) the arc \((i,j)\) is back in the residual network, so some augmentation in between, at a flow \(\vet{z}\), raised \(r_{ij}\): its path used the reverse arc \((j,i)\), and \(d_{\vet{z}}(i)=d_{\vet{z}}(j)+1\).

  3. The distances never decrease, so \(d_{\vet{z}}(j) \ge d_{\vet{x}}(j)\) and \(d_{\vet{y}}(i) \ge d_{\vet{z}}(i)\). Hence

    \[ d_{\vet{y}}(i) \ge d_{\vet{z}}(i)=d_{\vet{z}}(j)+1 \ge d_{\vet{x}}(j)+1=d_{\vet{x}}(i)+2 . \]

□

Theorem 5.15: running time of Edmonds–Karp

For any non-negative capacities, the Edmonds–Karp algorithm stops after at most \(n\,m\) augmentations with a maximum flow and a minimum cut, and it runs in \(O(n\,m\,(n+m))\) time, that is \(O(n\,m^2)\) when \(m \ge n-1\).

Proof

  1. Every augmentation has at least one critical arc: an arc of \(P\) whose residual capacity equals \(\delta\).

  2. When \((i,j)\) is critical, \(i\) lies before \(t\) on a path from \(s\) to \(t\) with at most \(n-1\) arcs, so \(0 \le d(i) \le n-2\). By Lemma 5.14 this distance grows by at least \(2\) between two critical times, so \((i,j)\) is critical at most \(\lfloor \frac{n-2}{2} \rfloor+1 \le \frac{n}{2}\) times.

  3. Every residual arc is \((i,j)\) or \((j,i)\) for an arc \((i,j) \in A\): there are at most \(2m\) of them, and at most \(2m \cdot \frac{n}{2}=n\,m\) augmentations.

  4. Every iteration takes \(O(n+m)\) time, as in Theorem 5.11. At the stop \(G(\vet{x})\) has no augmenting path, and Theorem 5.8 applies as in the proof of Theorem 5.9. □

  • The bound depends only on \(n\) and \(m\), not on the capacities: the Edmonds–Karp algorithm is strongly polynomial, and it stops also with irrational capacities.

5.6.1 Edmonds–Karp on the reference network

Example 5.8: Edmonds–Karp on the reference network

We run the algorithm on the network of Example 5.1; the column «arcs» is the number of arcs of the augmenting path.

iteration augmenting path arcs \(r_{ij}\) on \(P\) backward arcs \(\delta\) \(v\)
\(1\) \(1,2,4,6\) \(3\) \(5,3,4\) – \(3\) \(3\)
\(2\) \(1,3,5,6\) \(3\) \(4,4,3\) – \(3\) \(6\)
\(3\) \(1,3,5,4,6\) \(4\) \(1,1,2,1\) – \(1\) \(7\)

The distances \(d_{\vet{x}}(i)\) in the residual network before each search are:

iteration \(d(1)\) \(d(2)\) \(d(3)\) \(d(4)\) \(d(5)\) \(d(6)\)
\(1\) \(0\) \(1\) \(1\) \(2\) \(2\) \(3\)
\(2\) \(0\) \(1\) \(1\) \(3\) \(2\) \(3\)
\(3\) \(0\) \(1\) \(1\) \(3\) \(2\) \(4\)
stop \(0\) \(1\) \(\infty\) \(\infty\) \(\infty\) \(\infty\)

  • Iteration \(1\) is the breadth-first search of Chapter 1, Example «BFS from node \(1\)», whose tree path to node \(6\) is \(1,2,4,6\).

  • The critical arcs are \((2,4)\) in iteration \(1\), \((5,6)\) in iteration \(2\), and \((1,3)\), \((3,5)\), \((4,6)\) in iteration \(3\). When \((2,4)\) leaves the residual network, \(d(4)\) grows from \(2\) to \(3\); no distance ever decreases.

  • The algorithm needs \(3\) augmentations, against the \(5\) of Example 5.6, far below the bound \(n\,m=54\). It ends with the same maximum flow \(\tilde{\vet{x}}\), the unique one, and the same cut \(S=\{1,2\}\).

  • On the network of Example 5.7 the breadth-first search finds \(1,2,4\) and then \(1,3,4\), each with \(\delta=M\): two augmentations for every \(M\).

The Edmonds–Karp algorithm augments along paths with the fewest arcs, found by the breadth-first search. The distances from \(s\) in the residual network never decrease, every arc is critical at most \(\frac{n}{2}\) times, and the algorithm makes at most \(n\,m\) augmentations: \(O(n\,m^2)\) time, for any capacities.

Next: 5.7 Applications