Overview
Edmonds-Karp is an implementation of the Ford-Fulkerson method that always chooses an augmenting path with the fewest edges, using breadth-first search (BFS). After finding the path, it sends as much additional flow as possible along it, updates the residual capacities, and repeats until no augmenting path remains.
Key concepts
name: Core idea; description: The central focus of edmonds-karp algorithm is the capability described here: The Edmonds-Karp Algorithm is a maximum flow algorithm that uses breadth-first search to find the shortest augmenting path in the residual network. This path-selection rule provides a polynomial-time running-time guarantee.; name: Problem context; description: Edmonds-Karp Algorithm is relevant when a computational task requires the behavior or capability described by this topic.; name: Correct use; description: Before using edmonds-karp algorithm, check its assumptions, input requirements, expected output, and resource constraints.
Complexity
time: O(V × E²).; space: O(V + E) for an adjacency-list residual graph.; explanation: BFS takes O(V + E) time. The key theoretical result is that the number of augmentations is bounded by O(V × E), leading to the O(V × E²) total bound.
Example
scenario: A network contains several possible routes from a source to a sink.; description: BFS explores vertices level by level and chooses a route containing the fewest edges among the available augmenting paths.; illustration: If one available route contains two edges and another contains four edges, BFS chooses the two-edge route, provided both are valid in the residual network.; explanation: After the chosen path is augmented, the residual graph changes and BFS is run again.
Pseudocode
EDMONDS-KARP(G, s, t):
initialize all flows to 0
totalFlow = 0
while BFS finds a path P from s to t in the residual graph:
bottleneck = minimum residual capacity on P
update residual capacities along P
totalFlow = totalFlow + bottleneck
return totalFlow
Applications
Network flow optimization.; Bipartite matching.; Transportation and logistics.; Communication networks.; Resource allocation and scheduling.
Advantages
Provides a guaranteed polynomial-time running-time bound.; Uses a familiar BFS procedure.; Avoids the unpredictable path-selection behavior of arbitrary Ford-Fulkerson implementations.; Works with general nonnegative capacities.