Alex's Notes

Week 7 - Edmonds-Karp algorithm

1 min read

Week 7 - Edmonds-Karp algorithm

This algorithm is essentially the same as Ford-Fulkerson Algorithm but we use BFS instead of DFS to find the augmenting path in the residual network.

Edmonds-Karp algorithm

Edmonds-Karp algorithm

This is an algorithm to solve the max flow problem but also solves the min st-cut problem on a flow network . 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 .

From Claim 1 we know we only have to loop times.

To run each iteration we need need to update the path length number of edges in the graph which takes time. We need to run BFS which takes if we assume is connected. Then calculating and updating the weights also takes time. So all together a single iteration takes time.

Therefore together this takes times.

Proof of claims

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

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

Let be the augmenting path in to make for .

Let be the edge distance from to as produced by our run of the DFS to produce path .

Claim 1

Claim 1

The algorithm has at most loops. i.e. .

Proof

Note that as we let in each round of the algorithm we remove at least one edge of to make . (This isn’t to say the number of edges reduces each round - as we may add in more edges to than we have deleted.)

From Claim 2 we know each edge gets deleted and reinserted to at most times.

Therefore we can only iterate times. As there has to be an edge to remove.

Claim 2

Claim 2

For every edge , is deleted and reinserted to at most times.

Proof

Let then from Claim 3 every time we remove and add the distance between and increases by 2. As the distance between and can be at most . This can only happen less than times.

Claim 3

Claim 3

Suppose edge is removed from and added back to . Then .

Proof

As we delete from from Claim 5 therefore From Claim 4 we have that As we add to from Claim 5 therefore Combining this all together we have

Misplaced && \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 >[!important] Claim 4 > >For all $v \in V$ $dist_i(v) \leq dist_j(v)$ for all $j \geq i$. ### Proof Suppose an edge $(y,z)$ is added to the [[Residual Network (flow)|residual network]] $G^{f_i}$ to make $G^{f_{i+1}}$. From [[Edmonds-Karp algorithm#claim-5|Claim 5]] this means $(z,y) \in p_i$ a path generated by a run of [[Breath-first search (BFS)|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 >[!important] Claim 5 > >If we add $(y,z)$ to $G^{f_{i+1}}$ then $(z,y) \in p_{i}$. >If we remove $(y,z)$ from $G^{f_i}$ then $(y,z) \in p_i$. ## 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 (flow)|residual network]] $G^{f_i}$ to make $G^{f_{i+1}}$: - Add $(v,w)$ to $G^{f_{i+1}}$ if the [[Flow|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|flow]] is now full. - So $(v,w) \in p_i$. - Add $(w,v)$ to $G^{f_{i+1}}$ if the [[Flow|flow]] was empty. - So $(v,w) \in p_i$. - Remove $(w,v)$ from $G^{f_i}$ if the [[Flow|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$.Link to original

Graph View

Backlinks