Ford-Fulkerson is sometimes called a method because some parts of its protocol are left unspecified. Edmonds-Karp, on the other hand, provides a full specification. Most importantly, it specifies that breadth-first search should be used to find the shortest paths during the intermediate stages of the program.
Edmonds-Karp improves the runtime of Ford-Fulkerson, which is , to . This improvement is important because it makes the runtime of Edmonds-Karp independent of the maximum flow of the network, .
Finding the maximum flow for a network was first solved by the Ford-Fulkerson algorithm. A network is often abstractly defined as a graph, , that has a set of vertices, , connected by a set of edges, . There is a source, , and a sink, , 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 max-flow min-cut theorem, which then was used to create the Ford-Fulkerson algorithm.
Edmonds-Karp is identical to Ford-Fulkerson except for one very important trait. The search order of augmenting paths is well defined. As a refresher from the Ford-Fulkerson 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 , for a graph, , 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 will lose the amount of weight corresponding to that edge in the augmenting path. Each reverse edge 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.
Edmonds-Karp differs from Ford-Fulkerson in that it chooses the next augmenting path using breadth-first search (bfs). So, if there are multiple augmenting paths to choose from, Edmonds-Karp will be sure to choose the shortest augmenting path from the source to the sink.
In the Edmonds-Karp 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 Edmonds-Karp?
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.
The following is an example of basic, non-language specific pseudo-code for Edmonds-Karp:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
In this pseudo-code, 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 breadth-first 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
v is then set to be the parent, and the inner loop is repeated until it reaches the source vertex.
Edmonds-Karp relies on many of the proofs and complexities that were described for Ford-Fulkerson. To prove that this implementation runs in , 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 . 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 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 is the flow before such an augmentation, and that is the flow just after. So there is some vertex, , such that because our contradicting flow is less than the original flow. Also define a vertex, , such that there is a path from to via that is the shortest path from to in . Also say that the shortest path from to is 1 more than the shortest path from to for simplicity, so
The shortest path from to did not decrease with the new flow because of how we chose , so
However, the edge cannot be in the residual graph, . If it were, there would be the following relationships (note that we are using integer edge lengths):
This last equation violates the relationship
In other words, the shortest path did, in fact, not decrease with the flow . This proof by contradiction tells us that the shortest path increases monotonically in the residual graph, which bounds the length of one iteration of Edmonds-Karp to .
Number of iterations
The next proof concerns the number of iterations that Edmonds-Karp must go through to find the maximum flow of a network. The goal is to prove that there are iterations of Edmonds-Karp.
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 edges can becomes critical at most times.
Let and be vertices in the graph that are connected by an edge, and let be the source. When that edge is first critical, the distance relationship will be
Once this flow is augmented, as we have already seen, the edge will disappear from the residual network. This edge cannot reappear unless the flow from to is decreased, which only happens if the edge appears on an augmenting path. If is the flow when this happens, then
Recalling from the first proof in this section that , we have
This last equation is very important. It is saying that between the time that first became critical when flow was to when it next became critical when flow was the distance between the source and increased by at least 2.
The intermediate vertices on the shortest path from to cannot contain , , or , so the distance to vertex is at most . 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, can become critical at most times, for a total of times.
Because there are total pairs of vertices that can, for the edge , become critical times, the total number of iterations that Edmonds-Karp can go through is
Edmonds-Karp makes some important improvement on the Ford-Fulkerson algorithm. Ford-Fulkerson simply states that the flow increases by at least 1 in every iteration. Each iteration takes time. as we saw above. So, all Ford-Fulkerson can promise is that the maximum flow is found in , where is the maximum flow itself.
Edmonds-Karp 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 Edmonds-Karp runs each iteration in time and that there are at most iterations, Edmonds-Karp is bounded by .
Here is a Python implementation of Edmonds-Karp:
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 pseudo-code. The only big change is that breadth-first 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
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 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 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.
As expected, the maximum flow from the source to the sink is 2000000.