This is an algorithm to solve the max flow problem but also solves the min st-cut problem on a flow network $(G = (V,E), c, s, t)$. This is very similar to the Ford-Fulkerson Algorithm but with the use of BFS when picking the s-t path.

Algorithm

edmonds_karp(G, c, s, t)
	Input: A flow network.
	Output: A max flow on the network.
1. Set f(e) = 0 for all e in E.
2. Build the residual network G^f for the current flow f.
3. Check for any s-t paths p in G^f using BFS.
	1. If no such path then output f.
4. Given p let c(p) = min_{e in p} c^f(e).
5. Augment f by c(p) units along p.
	1. f(e) = f(e) + c(p) for forward edges.
	2. f(e) = f(e) - c(p) for backward edges.
6. Repeat from step 2.

Correctness

This proof is the same as Ford-Fulkerson Algorithm.

Run time

This takes $O(\vert E \vert^2 \cdot \vert V \vert)$.

From Claim 1 we know we only have to loop $\vert E \vert \cdot \vert V \vert /2$ times.

To run each iteration we need need to update the path length number of edges in the graph $G^f$ which takes $O(\vert V \vert)$ time. We need to run BFS which takes $O(\vert V \vert + \vert E \vert) = O(\vert E \vert)$ if we assume $G$ is connected. Then calculating $c(p)$ and updating the weights also takes $O(\vert V \vert)$ time. So all together a single iteration takes $O(\vert E \vert)$ time.

Therefore together this takes $O(\vert E \vert^2 \cdot \vert V \vert)$ times.

Proof of claims

A bit of notation will help us understand what is going.

Suppose we have flows $f_i$ during the course of the algorithm - with $f_1$ being the empty flow and $f_k$ being the returned flow.

Let $p_i$ be the augmenting path in $G^{f_i}$ to make $f_{i+1}$ for $1 \leq i < k$.

Let $dist_i: V \rightarrow \mathbb{N} \cup \{\infty\}$ be the edge distance from $s$ to $v$ as produced by our run of the DFS to produce path $p_i$.

Claim 1

Proof

Note that as we let $c(p_i) = \min_{e \in p_i} c^{f_i}(e)$ in each round of the algorithm we remove at least one edge of $G^{f_i}$ to make $G^{f_{i+1}}$. (This isn’t to say the number of edges reduces each round - as we may add in more edges to $G^f$ than we have deleted.)

From Claim 2 we know each edge gets deleted and reinserted to $G^f$ at most $\vert V \vert/2$ times.

Therefore we can only iterate $\vert E \vert \cdot \vert V \vert / 2$ times. As there has to be an edge to remove.

Claim 2

Proof

Let $e = (y,z)$ then from Claim 3 every time we remove and add $e$ the distance between $s$ and $y$ increases by 2. As the distance between $y$ and $s$ can be at most $\vert V \vert - 1$. This can only happen less than $\vert V \vert / 2$ times.

Claim 3

Proof

As we delete $(y,z)$ from $G^{f_i}$ from Claim 5 $(y,z) \in p_i$ therefore

$$dist_i(z) = dist_i(y) + 1.$$

From Claim 4 we have that

$$dist_i(z) \leq dist_{j-1}(z), \mbox{ and } dist_i(y) \leq dist_{j-1}(y).$$

As we add $(y,z)$ to $G^{f_{j+1}}$ from Claim 5 $(z,y) \in p_{j}$ therefore

$$dist_j(y) = dist_j(z) + 1.$$

Combining this all together we have

$$\begin{align*} dist_j(y) & = dist_j(z) + 1 & \mbox{from the last statment}\\ & \geq dist_i(z) + 1 & \mbox{from the second statement}\\ & \geq (dist_i(y) + 1) + 1 & \mbox{ from the first statement}\\ & \geq dist_i(y) + 2\end{align*}$$

as claimed.

Claim 4

Proof

Suppose an edge $(y,z)$ is added to the residual network $G^{f_i}$ to make $G^{f_{i+1}}$. From Claim 5 this means $(z,y) \in p_i$ a path generated by a run of BFS on $G^{f_i}$.

Therefore $dist_{i}(y) = dist_{i}(z) + 1$. After adding $(y,z)$ this means

$$dist_{i+1}(z) = \min\{dist_{i}(z), dist_{i}(z) + 2\} = dist_{i}(z)$$

so $dist_{i+1}(z)$ hasn’t decreased by adding $(y,z)$ however it may increase if we remove edges.

Therefore as the distance to the terminus of an edge being added hasn’t increased no other edge distances can increase. If we remove edges, distances between vertices can increase.

Claim 5

Proof

For a given edge $(v,w) \in E$ we have the following conditions for it to be added or removed from the residual network $G^{f_i}$ to make $G^{f_{i+1}}$:

• Add $(v,w)$ to $G^{f_{i+1}}$ if the flow was full on $(v,w)$ and was reduced by $p_i$.
  • So $(w,v) \in p_i$.
• Remove $(v,w)$ from $G^{f_i}$ if the flow is now full.
  • So $(v,w) \in p_i$.
• Add $(w,v)$ to $G^{f_{i+1}}$ if the flow was empty.
  • So $(v,w) \in p_i$.
• Remove $(w,v)$ from $G^{f_i}$ if the flow was positive and is now empty.
  • So $(w,v) \in p_i$.

So if we add $(y,z)$ to $G^{f_{i+1}}$ then $(z,y) \in p_i$.

Similarly if we remove $(y,z)$ from $G^{f_i}$ then $(y,z) \in p_i$.