EdmondsKarp

Edmon ds-Karp algorithm is an instance of the Ford-Fulkerson method for computing the maximum flow in a flow network. It improves upon the basic approach by choosing augmenting paths that are shortest in the number of edges, found via breadth-first search in the residual graph. The algorithm repeatedly finds an s-t path, determines the bottleneck capacity along that path, and augments the flow by that amount, updating the residual capacities accordingly.

The core concept is the residual graph, which reflects how much additional flow can be sent along each edge in the forward direction and how much flow can be sent backward to undo previous decisions. Each iteration uses BFS to locate an augmenting path from the source to the sink; if such a path exists, the flow is increased along that path by the smallest residual capacity on the path. This process continues until no augmenting path remains, at which point the current flow value is the maximum.

Edmonds-Karp was introduced by Jack Edmonds and Richard Karp in 1972 and is renowned for proving a polynomial-time bound for the maximum flow problem. Its worst-case running time is O(V E^2), where V is the number of vertices and E is the number of edges. While there are more sophisticated max-flow algorithms with faster practical performance on large networks, Edmonds-Karp remains a foundational and widely taught approach due to its conceptual simplicity and clear demonstration of key max-flow principles.

In practice, the algorithm can be implemented with adjacency lists and a queue for BFS, updating a residual capacity matrix or structure as flows are augmented. It is particularly valued in educational contexts for illustrating the interaction between flow augmentation and residual networks.