Edmonds–Karp algorithm

The Edmonds–Karp algorithm is a Ford–Fulkerson method that repeatedly augments flow along a shortest path in the residual graph, found by breadth-first search.

Residual graph: A directed graph encoding remaining capacities and possible flow reversals for a particular flow. Breadth-first search finds augmenting paths in this graph, whose edges change after every augmentation.
Flow conservation: The condition that incoming and outgoing flow balance at every vertex except the source and sink. Every augmentation preserves this balance at intermediate vertices.
Dinic's algorithm: A maximum-flow algorithm that repeatedly builds a level graph and sends blocking flows through it. It also uses BFS distances but processes many admissible paths per phase.
Time complexity: A measure of how an algorithm's running time grows with input size. Edmonds–Karp runs in O(VE²), where V and E count vertices and edges.
Augmenting path: A source-to-sink path in a residual graph along which additional flow can be sent. Each iteration selects a shortest augmenting path and increases flow by its bottleneck capacity.
Capacity constraint: The rule that flow on an edge cannot exceed that edge's capacity. Residual capacities encode how much each edge can still carry.
Push–relabel algorithm: A maximum-flow algorithm that maintains excess flow and vertex labels, pushing and relabeling locally. It computes maximum flow without repeatedly searching for complete augmenting paths.
Amortized analysis: A method for bounding the average cost per operation across a sequence of operations. The runtime proof tracks how often residual edges can become critical across augmentations.
Breadth-first search: A graph traversal that visits vertices in order of increasing distance from a starting vertex. It finds a residual path with the fewest edges, the defining choice in Edmonds–Karp.
Ford–Fulkerson method: A family of maximum-flow algorithms that repeatedly augments flow along residual source-to-sink paths. Edmonds–Karp is the version that selects paths by breadth-first search.

Linked from 7 pages