EdmondsKarp Algorithm
The EdmondsKarp Algorithm is a specific implementation of the FordFulkerson algorithm. Like FordFulkerson, EdmondsKarp is also an algorithm that deals with the maxflow mincut problem.
FordFulkerson is sometimes called a method because some parts of its protocol are left unspecified. EdmondsKarp, on the other hand, provides a full specification. Most importantly, it specifies that breadthfirst search should be used to find the shortest paths during the intermediate stages of the program.
EdmondsKarp improves the runtime of FordFulkerson, which is \(O\big(E \cdot f^{*}\big)\), to \(O\big(V \cdot E^2\big)\). This improvement is important because it makes the runtime of EdmondsKarp independent of the maximum flow of the network, \(f^{*}\).
Overview
Finding the maximum flow for a network was first solved by the FordFulkerson algorithm. A network is often abstractly defined as a graph, \(G\), that has a set of vertices, \(V\), connected by a set of edges, \(E\). There is a source, \(s\), and a sink, \(t\), which represent where the flow is coming from and where it is going to. Finding the maximum flow through a network was solved via the maxflow mincut theorem, which then was used to create the FordFulkerson algorithm.
EdmondsKarp is identical to FordFulkerson except for one very important trait. The search order of augmenting paths is well defined. As a refresher from the FordFulkerson wiki, augmenting paths, along with residual graphs, are the two important concepts to understand when finding the max flow of a network.
Augmenting paths are simply any path from the source to the sink that can currently take more flow. Over the course of the algorithm, flow is monotonically increased. So, there are times when a path from the source to the sink can take on more flow, and that is an augmenting path.
A residual graph, denoted as \(G_f\), for a graph, \(G\), shares the same set of vertices. It is the edges that are different. During each round of the algorithm, an augmenting path is found. After this path is found, the set of edges for the new residual graph changes. Along the path, each edge \(u, v\) will lose the amount of weight corresponding to that edge in the augmenting path. Each reverse edge \(v, u\) will gain that weight. Edges in the original graph that are not in the augmenting path are not affected. Once there are no paths from the source to the sink in the residual graph, the algorithm terminates.
EdmondsKarp differs from FordFulkerson in that it chooses the next augmenting path using breadthfirst search (bfs). So, if there are multiple augmenting paths to choose from, EdmondsKarp will be sure to choose the shortest augmenting path from the source to the sink.
In the EdmondsKarp algorithm, the set of augmenting paths to choose from is well defined. Which of the following options will be the next augmenting path chosen by EdmondsKarp?
The following graph shows a set of vertices and edges. Each edge shows two numbers: its current flow divided by its capacity. In this implementation, vertices are processed in alphabetical order for search.
Algorithm PseudoCode
The following is an example of basic, nonlanguage specific pseudocode for EdmondsKarp:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 

In this pseudocode, the flow is initially zero and the initial residual capacity array is all zeroes. Then, the outer loop executes until there are no more paths from the source to the sink in the residual graph (the number of these loops is proven in the section below).
Inside this loop, we are performing breadthfirst search to find the shortest path from the source to the sink that has available capacity. This small change to BFS is quite easy because we are using the residual capacity matrix F
which basically tells us whether there is available capacity on a given edge.
Once we have found a path with residual capacity, m
, we add that capacity to our current maximum flow. Then, the code backtracks through the network, starting with the sink t
. As it backtracks, it finds the parent of the current vertex which is defined as u
. Then, the code updates the residual flow matrix F
to reflect the newly found augmenting path capacity m
. v
is then set to be the parent, and the inner loop is repeated until it reaches the source vertex.
Complexity Proof
EdmondsKarp relies on many of the proofs and complexities that were described for FordFulkerson. To prove that this implementation runs in \(O(V \cdot E^2)\), two statements must be shown to be true. The first is that on each iteration of the algorithm, the shortest path between the source and all other vertices in the residual graph must increase monotonic. That is, it is always increasing. The second is that total number of flow augmentations is \(O(V \cdot E)\). If it is true that the shortest path is always increasing in the residual graph (and therefore decreasing in the original graph), and that there are at most \(V \cdot E\) flow augmentations, then the bound on the complexity will be well defined.
Monotonically increasing path length
To show that the shortest path for all vertices is always increasing in the residual graph, a contradiction can be considered. So, consider a flow augmentation that causes the shortest path to decrease. Imagine that \(f\) is the flow before such an augmentation, and that \(\acute{f}\) is the flow just after. So there is some vertex, \(v\), such that \(distance_{\acute{f}}(s, v) \lt distance_{f}(s, v)\) because our contradicting flow is less than the original flow. Also define a vertex, \(u\), such that there is a path from \(s\) to \(v\) via \(u\) that is the shortest path from \(s\) to \(v\) in \(G_f\). Also say that the shortest path from \(s\) to \(v\) is 1 more than the shortest path from \(s\) to \(u\) for simplicity, so
\[distance_{\acute{f}}(s, u) = distance_{\acute{f}}(s, v)  1.\]
The shortest path from \(s\) to \(u\) did not decrease with the new flow \(\acute{f}\) because of how we chose \(v\), so
\[distance_{\acute{f}}(s, u) \geq distance_{f}(s, u).\]
However, the edge \((u, v)\) cannot be in the residual graph, \(G_f\). If it were, there would be the following relationships (note that we are using integer edge lengths):
\[\begin{align} distance_f(s, v) &\leq distance_f(s, u) + 1 &&\qquad (\textrm{by the triangle inequality}) \\ distance_f(s, v) &\leq distance_{\acute{f}}(s, u) + 1 &&\qquad \big(\textrm{because the shortest path decreases with } \acute{f}\big)\\ distance_f(s, v) &\leq distance_{\acute{f}}(s, v). &&\qquad \big(\textrm{because of the relationship between (s, u) and (s, v)}\big) \end{align} \]
This last equation violates the relationship
\[distance_{\acute{f}}(s, v) \lt distance_f(s, v) .\]
In other words, the shortest path did, in fact, not decrease with the flow \(\acute{f}\). This proof by contradiction tells us that the shortest path increases monotonically in the residual graph, which bounds the length of one iteration of EdmondsKarp to \(O(E)\).
Number of iterations
The next proof concerns the number of iterations that EdmondsKarp must go through to find the maximum flow of a network. The goal is to prove that there are \(O(V \cdot E)\) iterations of EdmondsKarp.
An edge is defined as critical on an augmenting path if and only if the residual capacity of the edge equals the residual capacity of the path. In other words, the critical edge's capacity will be filled by this augmenting path. Once we have augmented this path, the edge in question will disappear from the residual network. We must show that each of the \(E\) edges can becomes critical at most \(\frac{V}{2}\) times.
Let \(u\) and \(v\) be vertices in the graph that are connected by an edge, and let \(s\) be the source. When that edge is first critical, the distance relationship will be
\[distance_f(s, v) = distance_f(s, u) + 1 .\]
Once this flow is augmented, as we have already seen, the edge \((u, v)\) will disappear from the residual network. This edge cannot reappear unless the flow from \(u\) to \(v\) is decreased, which only happens if the edge \((v, u)\) appears on an augmenting path. If \(\acute{f}\) is the flow when this happens, then
\[distance_{\acute{f}}(s, u) = distance_{\acute{f}}(s, v) + 1 .\]
Recalling from the first proof in this section that \(distance_f(s, v) \leq distance_{\acute{f}}(s, v)\), we have
\[\begin{align} distance_{\acute{f}}(s, u) &= distance_{\acute{f}}(s, v) + 1 \\ distance_{\acute{f}}(s, u) &\geq distance_{f}(s, v) + 1 \\ distance_{\acute{f}}(s, u) &\geq distance_{f}(s, u) + 2. \end{align}\]
This last equation is very important. It is saying that between the time that \((u, v)\) first became critical \((\)when flow was \(f),\) to when it next became critical \((\)when flow was \(\acute{f}),\) the distance between the source and \(u\) increased by at least 2.
The intermediate vertices on the shortest path from \(s\) to \(u\) cannot contain \(s\), \(u\), or \(t\), so the distance to vertex \(u\) is at most \(V  2\). The denominator of that fraction is 2 because the distance from the source increases by at least 2 every time an edge becomes critical. So, \((u, v)\) can become critical at most \(\frac{V  2}{2}\) times, for a total of \(O\big(V\big)\) times.
Because there are \(O\big(E\big)\) total pairs of vertices that can, for the edge \((u, v)\), become critical \(O\big(V\big)\) times, the total number of iterations that EdmondsKarp can go through is \(O\big(V \cdot E\big).\)
Complexity
EdmondsKarp makes some important improvement on the FordFulkerson algorithm. FordFulkerson simply states that the flow increases by at least 1 in every iteration. Each iteration takes \(O\big(E\big)\) time. as we saw above. So, all FordFulkerson can promise is that the maximum flow is found in \(O\big(E \cdot f^{*}\big)\), where \(f^{*}\) is the maximum flow itself.
EdmondsKarp removes the dependency on maximum flow for complexity, making it much better for graphs that have a large maximum flow, like this one:
By showing that EdmondsKarp runs each iteration in \(O\big(E\big)\) time and that there are at most \(V \cdot E\) iterations, EdmondsKarp is bounded by \(O\big(V \cdot E^2\big)\).
Sample Python Implementation
Here is a Python implementation of EdmondsKarp:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 

It closely follows the pseudocode. The only big change is that breadthfirst search is abstracted away into its own function due to Python scoping reasons.
If we take the graph from the complexity section, we can use this code to solve for its maximum flow. First we need to define the inputs, the adjacency matrix E
, the capacity matrix C
, the source s
, and the sink t
.
1 2 3 4 

All that's happened here is that we've numbered the 4 vertices in the graph. The source is 0, A is 1, B is 2, and the sink is 3. In the adjacency matrix, the fact that [1, 2]
is the \(0^\text{th}\) index of the list means that there is an edge from 0 to 1 and from 0 to 2. In the capacity matrix C
, the fact that [0, 1000000, 1000000, 0]
is in the \(0^\text{th}\) index means that there is 0 capacity from 0 to 0 and from 0 to 3 and that there is 1000000 capcity from 0 to 1 and from 0 to 2. Remember that Python uses 0 indexing!
Now we can run the code.
1 2 

As expected, the maximum flow from the source to the sink is 2000000.