Edmonds–Karp Algorithm
Edmonds–Karp is Ford–Fulkerson with one disciplined choice: always augment along a residual path with the fewest edges. BFS finds that path because every residual arc counts as one step, regardless of capacity. This turns an arbitrary augmenting-path process into a polynomial-time algorithm independent of capacity magnitudes. It is easy to inspect and useful as a correctness reference for faster flow implementations.
Prerequisites: Ford–Fulkerson Algorithm; Breadth-first search. Difficulty: Advanced. Review: Breadth-first search, Ford–Fulkerson Algorithm.
Build the idea
1. Search residual distance layers
Initialize parent[s] with a special sentinel and enqueue s. For every dequeued vertex, follow only positive-capacity residual arcs to undiscovered vertices. First discovery gives a shortest edge-count route. Original edge capacities are not lengths: an arc of capacity 100 and one of capacity 1 each advance exactly one BFS level. Mark on enqueue, preventing repeated visits and parent cycles.
2. Remember which edge discovered a vertex
parent[u] stores an edge ID. Its paired reverse edge points back to the predecessor. This supports parallel input edges correctly: two edges joining the same pair may have different remaining capacities. Reconstruct from t to s once to find the minimum capacity, then again to perform equal forward decreases and reverse increases. The source sentinel must never be mistaken for an ordinary edge.
3. Walk through the sample
BFS first finds 1→2→4, bottleneck 2. A second BFS finds 1→3→4, bottleneck 2. The remaining unit travels 1→2→3→4. Residual reverse arcs are present after each pass even when this particular sample does not need cancellation. The answer is 2+2+1=5. A fresh BFS sees no s→t route, so the loop returns. A search timestamp marks discoveries without clearing a V-sized array each time; parent entries from older searches are ignored.
Augmentation Path Added Total 1 1→2→4 2 2 2 1→3→4 2 4 3 1→2→3→4 1 5 4. Understand the polynomial argument
Residual shortest distances from s never decrease after a shortest-path augmentation. A newly available reverse arc runs backward across one previous BFS layer, so it cannot create a shorter route. Every augmentation saturates at least one residual arc. Before the same directed residual arc can be saturated again on a shortest path, flow must first travel back through its partner; this forces its tail distance to increase by at least two. Distances are below V while reachable, so each of O(E) arcs is critical O(V) times. There are O(VE) augmentations.
5. Separate optimality from speed
The max-flow/min-cut argument proves correctness exactly as in Ford–Fulkerson; BFS supplies the runtime guarantee, not a different feasibility rule. One BFS plus reconstruction scans O(E) reachable residual data plus constant source work. Timestamp marks avoid repeatedly clearing arrays for irrelevant isolated vertices. Combining O(VE) augmentations with O(E) search work gives the conventional O(VE²) bound, plus one-time O(V+E) initialization. Integer capacities avoid numerical roundoff, although the combinatorial augmentation bound does not depend on F.
C++17 implementation
This is a complete program. Compile with C++17 and enter the input described below.
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<limits>
using namespace std;
using ll=long long;
struct Edge{
int to;
ll cap;
};
vector<Edge>edges;
vector<vector<int>>graph;
void addEdge(int u,int v,ll cap){
int id=(int)edges.size();
edges.push_back({v,cap});
edges.push_back({u,0}); // Reverse residual edge starts empty.
graph[u].push_back(id);
graph[v].push_back(id^1); // Works even for self-loops and parallel edges.
}
ll maxFlow(int n,int s,int t){
ll answer=0,search=0;
vector<int>parent(n+1,-1);
vector<ll>marked(n+1,0); // Timestamps avoid clearing isolated vertices per BFS.
for(;;){
++search;
queue<int>q;
parent[s]=-2;
marked[s]=search;
q.push(s);
while(!q.empty()&&marked[t]!=search){
int v=q.front();
q.pop();
for(int id:graph[v]){
int u=edges[id].to;
if(edges[id].cap>0&&marked[u]!=search){
marked[u]=search;
parent[u]=id;
q.push(u); // Store the edge, not just vertex.
}
}
}
if(marked[t]!=search){
return answer;
}
ll pushed=numeric_limits<ll>::max();
for(int v=t;v!=s;v=edges[parent[v]^1].to){
pushed=min(pushed,edges[parent[v]].cap);
}
for(int v=t;v!=s;v=edges[parent[v]^1].to){
int id=parent[v];
edges[id].cap-=pushed;
edges[id^1].cap+=pushed;
}
answer+=pushed;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m,s,t;
if(!(cin>>n>>m>>s>>t)){
return 0;
}
graph.resize(n+1);
for(int i=0;i<m;++i){
int u,v;
ll c;
cin>>u>>v>>c;
addEdge(u,v,c);
}
cout<<maxFlow(n,s,t)<<'\n';
}
Complexity analysis
O(VE²) standard worst-case flow time, plus O(V+E) initialization; O(V+E) memory. A timestamped BFS scans only reachable residual arcs, and there are O(VE) augmentations. Even an edgeless input only pays the one-time vertex allocation. Edge capacities, timestamps and accumulated answer use long long.
Example input and output
Read n m s t, then m directed edges u v capacity. Vertices are 1..n, n≥2, s≠t. Parallel and opposite-direction edges are allowed. Capacities are nonnegative integers; total capacity leaving s fits long long (at most 10^15 here). Output the maximum flow value.
Input
4 5 1 4 1 2 3 1 3 2 2 3 1 2 4 2 3 4 3
Output
5
Shortest residual paths deliver two units, then two, then one. Source outgoing capacity 5 proves no larger answer is possible.
Practical applications
Use for small or medium flow networks, teaching, and randomized cross-checking of Dinic. It is generally slower than Dinic on large instances because it rebuilds BFS after every individual path rather than sending a blocking flow through one level graph. A weighted assignment objective requires minimum-cost flow or Hungarian, not plain max flow.
Check your understanding
What does “shortest” mean in Edmonds–Karp?
Put it into practice
Instrument the code to print the length of each augmenting path.
Show a hint
Record BFS depth; these source-to-sink lengths cannot decrease.