Network Flow: Edmonds-Karp Algorithm | Baeldung on Computer Science

1. Introduction

In this tutorial, we’ll explore the Edmonds-Karp algorithm for finding the maximum flow in network graphs. It’s a variant of the Ford-Fulkerson method, where augmenting paths are identified using breadth-first search (BFS).

2. Definitions

In this section, we define the network flow-related notions required throughout our discussion. We assume we’re given a directed graph $G = (V, E)$ , where $V$ is the set of vertices, and $E$ is the set of edges of the graph. We also assume that the size of $V$ is $N$ and the size of $E$ is $M$ .

2.1. Network Graph

In the maximum flow problem, we are given a network graph, and we need to find the maximum flow that can go from a source vertex, $S$ , to a sink vertex, $T$ . A network graph is a directed graph where each edge is assigned a non-negative capacity. That is, there’s a non-negative capacity function defined on the edges of the graph: $\textrm{C}: V \times V \rightarrow R$ . $C$ satisfies the following conditions:

$C(u, v) \ge 0, (u, v) \in G.E$
$C(u, v) = 0, (u, v) \notin G.E$

We also define a non-negative function of flow defined on the edges of $G$ : $\textrm{F}: V \times V \rightarrow R$ . $F$ also conforms to several conditions:

$F(u, v) \ge 0, (u, v) \in G.E$
$F(u, v) = 0, (u, v) \notin G.E$
$\forall (u, v), F(u, v) \le C(u,v)$

The last condition simply means that the edge capacities constrain the flow and can’t exceed them.

Finally, we assume $G$ doesn’t contain reverse edges. That is, if $(u, v) \in E$ , then $(v, u) \notin E$ . The reverse edges are not allowed because they constructively appear in the residual graph to find the maximum flow. Actually, we can get an equivalent graph without reverse edges from the original graph with reverse edges by introducing new vertices:

We perform the transformation above for all the reverse edges in the graph.

2.2. Residual Graph

The residual graph, $R_G$ , of $G$ is defined in the following way: $G_R = (G.V, E_R)$ , where $(u, v) \in E_R$ if $C(u, v) - F(u,v ) > 0$ in $G$ . Shortly, $G_R$ consists of the same vertices as $G$ , and any edge $(u, v) \in G.E$ is present in $E_R$ if $(u, v)$ has the potential to conduct more flow. If for edge $(u, v) \in E$ , $C(u, v) - F(u, v) = 0$ , that means the edge’s capacity is fully used, and it can’t accept any more flow. Such an edge is absent in $E_R$ .

Additionally, we include reverse edges in $E_R$ . Reverse edges are absent in $E$ and may appear in $E_R$ while running the Ford-Fulkerson method. If edge $(u, v) \in E$ currently conducts the flow of value $F(u, v)$ , then we add edge $(v, u)$ to $E_R$ with residual capacity $F(u, v)$ .

Finally, we define a positive function of residual capacities on the edges of $E_R$ : $\textrm{C_R}: V \times V \rightarrow R$ . $C_R$ is defined as:

$C_R(u, v) = C(u, v) - F(u, v), (u, v) \in E$ and $C(u, v) - F(u, v) > 0$
$C_R(v, u) = F(u, v), (u, v) \in E$ and $F(u, v) > 0$

2.3. Augmenting Paths

An augmenting path is any path from $\boldsymbol{S}$ to $\boldsymbol{T}$ in $\boldsymbol{G_R}$ . They’re used by the algorithm to increase the flow from $S$ to $T$ gradually.

3. Edmonds-Karp Algorithm

3.1. Algorithm Demonstration

Assume we have a network graph shown below. The edge capacities are depicted as well:

Let’s show how the Edmonds-Karp algorithm works by finding the maximum flow on the graph step by step. Initially, we build $G_R$ , which fully matches $G$ as there’s no flow in $G$ yet. Below, we can see $G_R$ on the left and $G$ on the right. For the edges of $G$ , we depict the current flow on them followed by their capacity:

Next, we find the first shortest path from $S$ to $T$ using BFS. The path consists of three edges and is shown on $G_R$ below. The flow increases by 8 along the augmenting path. We parallelly change the flow across the edges of $G$ as the algorithm progresses:

As the flow changes, new reverse edges may appear in $G_R$ . Below, we can see new reverse edges, along with the second shortest path from $S$ to $T$ consisting of four edges. The flow increases by 5 this time:

Next, we find another augmenting path consisting of four edges. The path increases the flow by 2:

We’re in a situation now where there’re no augmenting paths left in $G_R$ . It’s the indication that the algorithm has finished and we’ve found the maximum flow from $S$ to $T$ :

The maximum flow value may be fetched by either adding the flows on the outgoing edges of $S$ or by adding the flows on the incoming edge of $T$ . In either case, the maximum flow value is 15 for our example.

3.2. Algorithm Pseudocode

The pseudocode of the Edmonds-Karp algorithm is almost the same as the one for the Ford-Fulkerson method. The difference is that the Ford-Fulkerson method doesn’t specify how augmenting paths are found, while the Edmonds-Karp algorithm states they’re found using BFS. We can find the pseudocode of the Edmonds-Karp algorithm below:

3.3. Algorithm Complexity

The drawback of the Ford-Fulkerson method is that it may run in exponential time. Its time complexity is $\boldsymbol{O(M * F_{max})}$ , where $\boldsymbol{F_{max}}$ is the value of the maximum flow. So, the method’s time complexity depends on the maximum flow value. It effectively means that we may have various performances by changing the capacity function on the same graph. Additionally, the Ford-Fulkerson method may never end if the capacities of the edges are irrational.

The Edmonds-Karp algorithm fixes the drawbacks as it runs in polynomial time: $\boldsymbol{O(N * M^2)}$ . The complexity follows from the observation that there can’t be more than $\boldsymbol{O(N * M)}$ flow augmentations, and each flow augmentation runs in $\boldsymbol{O(M)}$ .

4. Conclusion

In this tutorial, we’ve discussed the Edmonds-Karp algorithm for finding the maximum flow in network graphs. It’s a customization of the Ford-Fulkerson method where augmenting paths are found using BFS. The algorithm is polynomial.

Full Archive

About Baeldung

Core Concepts

Operating Systems

Artificial Intelligence

Graph Theory

Latex