Edmonds-Karp Algorithm

The Edmonds-Karp Algorithm is a specific implementation of the Ford-Fulkerson algorithm. Like Ford-Fulkerson, Edmonds-Karp is also an algorithm that deals with the max-flow min-cut problem.

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 \(O\big(|E| \cdot f^{*}\big)\), to \(O\big(|V| \cdot |E|^2\big)\). This improvement is important because it makes the runtime of Edmonds-Karp independent of the maximum flow of the network, \(f^{*}\).

Finding the maximum flow for a network was first solved by the Ford-Fulkerson 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 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 \(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.

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.

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

inputs
    C[n x n] : Capacity Matrix
    E[n x n] : Adjacency Matrix
    s : source
    t : sink
output
    f : maximum flow
Edmonds-Karp:
    f = 0                // Flow is initially 0
    F = [n x n]       // residual capacity array
    while true:
        m, P = Breadth-First-Search(C, E, s, t, F)
        if m = 0:
            break
        f = f + m
        v = t
        while v != s:
            u = P[v]
            F[u, v] = F[u, v] - m       //This is reducing the residual capacity of the augmenting path
            F[v, u] = F[v, u] + m        //This is increasing the residual capacity of the reverse edges 
            v = u
    return f

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 m. 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 \(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 Edmonds-Karp to \(O(E)\).

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 \(O(V \cdot E)\) 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 \(|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 Edmonds-Karp can go through is \(O\big(|V| \cdot |E|\big).\)

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 \(O\big(|E|\big)\) time. as we saw above. So, all Ford-Fulkerson can promise is that the maximum flow is found in \(O\big(|E| \cdot f^{*}\big)\), where \(f^{*}\) 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:

Graph with large maximum flow but few edges and vertices

By showing that Edmonds-Karp runs each iteration in \(O\big(|E|\big)\) time and that there are at most \(|V| \cdot |E|\) iterations, Edmonds-Karp is bounded by \(O\big(|V| \cdot |E^2|\big)\).

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

import decimal

def EdmondsKarp(E, C, s, t):
    n = len(C)
    flow = 0
    F = [[0 for y in range(n)] for x in range(n)]
    while True:
        P = [-1 for x in range(n)]
        P[s] = -2
        M = [0 for x in range(n)]
        M[s] = decimal.Decimal('Infinity')
        BFSq = []
        BFSq.append(s)
        pathFlow, P = BFSEK(E, C, s, t, F, P, M, BFSq)
        if pathFlow == 0:
            break
        flow = flow + pathFlow
        v = t
        while v != s:
            u = P[v]
            F[u][v] = F[u][v] + pathFlow
            F[v][u] = F[v][u] - pathFlow
            v = u
    return flow

def BFSEK(E, C, s, t, F, P, M, BFSq):
    while (len(BFSq) > 0):
        u = BFSq.pop(0)
        for v in E[u]:
            if C[u][v] - F[u][v] > 0 and P[v] == -1:
                P[v] = u
                M[v] = min(M[u], C[u][v] - F[u][v])
                if v != t:
                    BFSq.append(v)
                else:
                    return M[t], P
    return 0, P

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 t.

1
2
3
4

>>> E = [[1, 2], [2, 3], [3], []]
>>> C = [[0, 1000000, 1000000, 0], [0, 0, 1, 1000000], [0, 0, 0, 1000000], [0, 0, 0, 0]]
>>> s = 0
>>> t = 3

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

>>> EdmondsKarp(E, C, s, t)
2000000

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