Dinic's Algorithm
Dinic accelerates maximum flow by grouping augmentations into phases. BFS first builds shortest residual distance layers. DFS then sends as much flow as needed to block every source-to-sink route that respects those layers. Many paths share one BFS computation, which often makes this a practical default for competitive-programming flow networks. The general guarantee is O(V²E); the much better O(E√V) bound belongs to special unit networks such as bipartite matching, not arbitrary capacities.
Prerequisites: Edmonds–Karp Algorithm; DFS recursion and references. Difficulty: Advanced. Review: Edmonds–Karp Algorithm.
Build the idea
1. Build the level graph
level[v] is the minimum number of positive residual arcs from s to v. Only edges with level[u] = level[v]+1 are admissible for this phase. Their levels strictly increase, so this temporary graph has no directed cycles even if the residual network does. If t is unreachable, residual optimality proves the current flow is maximum.
2. Send a blocking flow
send(v,t,limit) descends through admissible edges and returns a bottleneck. Successful recursion updates residual partners exactly as before. Keep calling send from s until it returns zero. “Blocking” means every admissible s→t path now contains a saturated edge; it does not require a maximum flow under arbitrary rerouting inside the level graph. Reverse arcs created during this phase point toward earlier levels, so they cannot become new admissible forward steps.
3. Reuse current-edge pointers
nextEdge[v] remembers the first adjacency entry not yet ruled out. It is a reference in the for-loop: advancing it must persist across calls. An arc with no residual capacity, wrong level, or no remaining route to t cannot become useful again in this phase. Successful arcs stay current until saturated or their suffix is exhausted. Reset these pointers only after the next BFS, because admissibility can then change.
4. Trace phases on the example
The first BFS places {1} at level 0, {2,3} at level 1 and {4} at level 2. Paths 1→2→4 and 1→3→4 each carry 2; the edge 2→3 is not admissible because both endpoints currently have level 1. After blocking these paths, rebuild BFS. The residual path 1→2→3→4 now has length 3 and carries 1. The total reaches 5.
Phase Distance to sink Flow added 1 2 4 2 3 1 5. Reason about progress and cost
After a blocking flow, the shortest residual s→t distance strictly increases. Otherwise a shortest route of the old length would use only old forward-level edges, contradicting the blocking property. The distance can increase fewer than V times. With current-edge pointers, a blocking flow costs O(VE): O(E) pointer advances plus at most O(E) successful paths of length O(V). Multiply by O(V) phases. This proof is about general networks; special structures admit sharper analyses.
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.
}
vector<int>level,nextEdge;
bool buildLevels(int n,int s,int t){
level.assign(n+1,-1);
queue<int>q;
level[s]=0;
q.push(s);
while(!q.empty()){
int v=q.front();
q.pop();
for(int id:graph[v]){
int u=edges[id].to;
if(edges[id].cap>0&&level[u]==-1){
level[u]=level[v]+1;
q.push(u);
}
}
}
return level[t]!=-1;
}
ll send(int v,int t,ll limit){
if(v==t){
return limit;
}
for(int&i=nextEdge[v];i<(int)graph[v].size();++i){
int id=graph[v][i],u=edges[id].to;
if(edges[id].cap==0||level[u]!=level[v]+1){
continue;
}
ll pushed=send(u,t,min(limit,edges[id].cap));
if(!pushed){
continue;
}
edges[id].cap-=pushed;
edges[id^1].cap+=pushed;
return pushed;
}
return 0;
}
ll maxFlow(int n,int s,int t){
ll answer=0;
while(buildLevels(n,s,t)){
nextEdge.assign(n+1,0);
// Reuse this level graph until every s-t path in it is blocked.
while(ll pushed=send(s,t,numeric_limits<ll>::max())){
answer+=pushed;
}
}
return answer;
}
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(V²E) general worst-case time, with O(V+E) memory for residual edges, levels, pointers, queue and recursion. A level-graph BFS costs O(V+E), and a general blocking-flow phase costs O(VE). On unit networks arising from bipartite matching, O(E√V) is available; do not use that bound for arbitrary input capacities.
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
The first blocking-flow phase sends 4 units along length-two paths; the next phase sends the final unit along a length-three path.
Practical applications
Use Dinic for general capacity networks, edge-disjoint paths and flow reductions with many augmenting paths. Use direct Hopcroft–Karp for large unweighted bipartite matching. Edmonds–Karp remains easier for debugging and small reference solutions; neither plain solver optimizes edge costs.
Check your understanding
When should current-edge pointers be reset?
Put it into practice
Count BFS phases and DFS edge inspections on a network with many disjoint s→t paths.
Show a hint
Compare one phase sending many paths with Edmonds–Karp rebuilding BFS for each path.