Edmonds–Karp algorithm

The Edmonds–Karp algorithm is an algorithm for computing the maximum flow in a flow network, representing a specific implementation of the Ford–Fulkerson method that selects augmenting paths using breadth-first search (BFS) to ensure the shortest path in terms of the number of edges is chosen at each iteration.^[1] This approach refines the original Ford–Fulkerson method by avoiding poor path selections that could lead to exponential running times, instead guaranteeing polynomial-time performance through a controlled number of augmentations.^[2] Developed by Jack Edmonds and Richard M. Karp in 1972, the algorithm builds on the labeling procedure of Ford–Fulkerson by employing a "first-labeled first-scanned" rule, which effectively implements BFS to identify the minimal-length augmenting paths in the residual graph.^[1] The number of augmentations is bounded by O(VE), where V is the number of vertices and E is the number of edges, since each augmentation increases the shortest-path distances in the residual graph, and BFS takes O(E) time per augmentation, yielding an overall time complexity of O(VE²).^[3] This polynomial bound holds regardless of edge capacities, making it suitable for networks with real-valued capacities.^[2] The algorithm's significance lies in its role as one of the first provably efficient max-flow algorithms, influencing subsequent developments like Dinic's algorithm, and its practical simplicity due to the use of standard BFS, which makes it accessible for implementation in graph libraries and applications such as bipartite matching and transportation problems.^[1] While faster algorithms exist for dense graphs, Edmonds–Karp remains a foundational method taught in algorithms courses for demonstrating how heuristic choices in path selection can achieve theoretical efficiency guarantees.^[3]

Introduction

Overview

The Edmonds–Karp algorithm is a specific implementation of the Ford–Fulkerson method for computing the maximum flow in a flow network.^[4] It operates by repeatedly finding and augmenting along shortest augmenting paths in the residual graph, measured by the minimum number of edges (arcs).^[4] This approach uses breadth-first search (BFS) to identify such paths efficiently.^[1] The primary purpose of the algorithm is to determine the maximum possible flow from a designated source vertex to a sink vertex in a capacitated, directed graph, while also providing a valid flow assignment that achieves this value.^[4] It addresses the maximum flow problem, which models scenarios such as transportation networks, resource allocation, and communication systems where capacities limit the throughput between nodes.^[4] A key innovation of the Edmonds–Karp algorithm is its selection of shortest augmenting paths, which ensures termination in polynomial time and avoids the potential exponential slowdown of arbitrary path choices in the general Ford–Fulkerson method.^[4] By bounding the number of augmentations to at most O(VE) for a graph with |V| vertices and E edges, it guarantees efficient computation even for networks with integral capacities.^[4] The algorithm takes as input a flow network G = (V, E) with nonnegative capacity function c: V \times V \to \mathbb{R}_{\geq 0} and designated source s and sink t; it outputs the maximum flow value and a corresponding flow function f: V \times V \to \mathbb{R}_{\geq 0}.^[4]

History

The Edmonds–Karp algorithm was developed by Jack Edmonds and Richard M. Karp in 1972 as an improvement to existing network flow techniques. It was first described in their seminal paper "Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems," published in the Journal of the Association for Computing Machinery.^[4] This work introduced a specific implementation of the augmenting path method that ensured polynomial-time performance. The approach was independently discovered by Yefim Dinic in 1970.^[5] The algorithm addressed a key limitation in the foundational Ford–Fulkerson method, proposed by Lester R. Ford Jr. and Delbert R. Fulkerson in 1956, which could exhibit exponential runtime in the worst case due to poor choices of augmenting paths.^[6] By restricting the search for augmenting paths to breadth-first search, Edmonds and Karp provided a strongly polynomial-time algorithm for maximum flow computation, achieving a time bound of O(VE²), where V is the number of vertices and E is the number of edges.^[4] Edmonds' earlier contributions to combinatorial optimization, including his development of matroid intersection theory and polynomial-time algorithms for bipartite matching in the 1960s, laid important groundwork that influenced the algorithmic approaches to network flows.^[7] These advancements in matroid theory and matching problems helped bridge abstract combinatorial structures with practical flow models. Owing to its conceptual simplicity and rigorous efficiency guarantees, the Edmonds–Karp algorithm quickly became a standard pedagogical example for illustrating polynomial-time solutions to the maximum flow problem in academic settings.^[8]

Background

Flow Networks

A flow network is modeled as a directed graph G = (V, E) with a source vertex s \in V, a sink vertex t \in V \setminus \{s\}, and a non-negative capacity function c: V \times V \to \mathbb{R}_{\geq 0} defined for all pairs of vertices, where c(u,v) > 0 indicates the presence of a directed edge from u to v with maximum allowable flow equal to that capacity.^[9] This structure represents systems where commodities or resources flow from the source to the sink subject to edge-specific limits, such as transportation or communication networks.^[9] A valid flow f: V \times V \to \mathbb{R} in the network must satisfy three key properties: the capacity constraint, which requires |f(u,v)| \leq c(u,v) for all u, v \in V; skew symmetry, ensuring f(u,v) = -f(v,u) for all u, v \in V; and flow conservation, stating that \sum_{v \in V} f(u,v) = 0 for every vertex u \in V \setminus \{s, t\}.^[9] The value of such a flow, denoted |f|, is the net outflow from the source, given by |f| = \sum_{v \in V} f(s,v), which equals the net inflow to the sink -\sum_{u \in V} f(t,u) by conservation.^[9] The maximum flow problem seeks a valid flow f that maximizes this value |f|.^[9] This problem is addressed by the Ford–Fulkerson method, a foundational iterative approach for computing maximum flows.^[6] Given a flow f, the residual graph G_f = (V, E_f) captures the remaining flow potential, with residual capacities c_f(u,v) = c(u,v) - f(u,v) for edges where flow can still increase forward, and c_f(u,v) = c(u,v) + f(v,u) otherwise to account for possible reductions via backward edges when existing flow exceeds zero in the opposite direction.^[9] The edge set E_f includes all pairs (u,v) where c_f(u,v) > 0, thus incorporating both original edges with unused capacity and reverse edges to "undo" prior flow allocations.^[9] An augmenting path in G_f is defined as a simple path from s to t where every edge has positive residual capacity, allowing additional flow to be pushed through the network without violating constraints.^[9] Such paths are central to flow augmentation strategies, as their bottleneck residual capacity determines the maximum increasable flow value along that route.^[9]

Ford–Fulkerson Method

The Ford–Fulkerson method provides a foundational framework for solving the maximum flow problem in flow networks by iteratively improving an initial feasible flow until optimality is reached. The algorithm initializes the flow to zero across all edges and proceeds by repeatedly searching for an augmenting path in the residual graph—a directed graph that represents the remaining capacities after accounting for the current flow. An augmenting path is a simple path from the source vertex s to the sink vertex t in this residual graph. Each time such a path is found, the algorithm augments the flow along it, increasing the total flow value by the maximum possible amount without violating capacity constraints. This process continues until no augmenting path exists, at which point the current flow is maximum.^[6] Augmentation along an identified path P involves computing the bottleneck capacity, defined as the minimum residual capacity over all edges in P:

b(P) = \min_{e \in P} c_f(e),

where c_f(e) denotes the residual capacity of edge e under the current flow f, given by c_f(e) = c(e) - f(e) for forward edges and c_f(e) = f(e) for backward edges in the residual graph. The flow is then updated by adding b(P) to the flow on each forward edge in P and subtracting b(P) from the flow on each corresponding backward edge, ensuring flow conservation and non-negativity are maintained. This step effectively "pushes" additional flow through the network while respecting edge capacities.^[6] The method's correctness relies on the max-flow min-cut theorem, which establishes that the value of the maximum flow from s to t equals the capacity of the minimum s- t cut—a partition of vertices into sets S (containing s) and T (containing t) where the cut capacity is the sum of capacities of edges from S to T. Upon termination, the absence of an augmenting path implies that the residual graph has no s- t path, which corresponds to the existence of a saturating cut whose capacity matches the current flow value, confirming optimality.^[6] A key limitation of the general Ford–Fulkerson method arises from its dependence on the choice of augmenting paths; selections via methods like depth-first search can lead to exponentially many iterations in the worst case, especially when capacities are irrational numbers or large integers that result in tiny augmentations per step. This can cause the algorithm to fail to terminate in polynomial time, highlighting the need for specialized path-finding strategies to achieve efficiency.^[10]

Algorithm

Augmenting Paths

In the Edmonds–Karp algorithm, augmenting paths are identified within the residual graph G_f, which captures the remaining capacities after previous flow augmentations. The algorithm employs breadth-first search (BFS) to locate the shortest augmenting path from the source vertex s to the sink vertex t, measured by the minimum number of edges. This selection distinguishes the Edmonds–Karp method from more general implementations of the Ford–Fulkerson algorithm by guaranteeing paths of minimal length in each iteration.^[1] The BFS procedure operates by initializing a queue with the source s at level 0 and systematically exploring adjacent vertices in a layer-by-layer manner. Vertices are assigned to levels L_i based on their shortest-path distance from s, traversing only edges (u, v) where the residual capacity c_f(u, v) > 0. During traversal, parent pointers are recorded for each newly visited vertex to enable path reconstruction; the search terminates upon reaching t, at which point the path is traced backward from t to s using these pointers. This process ensures the discovered path adheres strictly to the level structure, confirming its status as the shortest.^[11]^[1] The use of BFS is essential because it enforces the selection of shortest paths, preventing the algorithm from repeatedly using longer routes that could lead to inefficient progress. As a result, the lengths of successive augmenting paths are non-decreasing, which bounds the total number of such paths to O(VE) in a graph with V vertices and E edges. This property arises from the fact that once a path of a certain length is augmented, no shorter path can reappear in future residual graphs without violating the level-based exploration.^[1]^[12] Each iteration of the algorithm relies on BFS to uncover precisely one shortest augmenting path, without incorporating mechanisms like capacity scaling or multiple-path discovery heuristics. This focused approach maintains simplicity while achieving the desired efficiency guarantees.^[11]^[1]

Flow Updates

The Edmonds–Karp algorithm initializes the flow function f to zero for all edges in the flow network, ensuring no initial flow traverses any edge.$$] Upon discovering an augmenting path P from the source s to the sink t in the residual graph via breadth-first search, the algorithm computes the bottleneck capacity b, defined as the minimum residual capacity along the edges in P: [ b = \min_{(u,v) \in P} c_f(u,v)