Ford–Fulkerson Algorithm

Ford–Fulkerson is the augmenting-path method for maximum flow. Start with zero flow, find any residual path from s to t, send its bottleneck capacity, and repeat. The path-finding policy matters: this lesson uses DFS, making the method compact but potentially slow. It is valuable for learning residual reasoning and for small integer-capacity problems; it is not a universal fast maximum-flow algorithm.

Prerequisites: Introduction to Network Flow; Depth-first search. Difficulty: Advanced. Review: Depth-first search, Introduction to Network Flow.

Build the idea

1. 1. Store paired residual edges

   Each call to addEdge appends two entries to edges: the original residual capacity and its initially empty reverse. Adjacency lists store edge IDs, so id XOR 1 finds the exact partner. This avoids ambiguous matrix updates when parallel edges or genuine opposite-direction edges exist. Although our original network may contain cycles, seen[] makes each DFS a simple reachability search.

2. 2. Find and augment one path

   dfs(v,t,limit) returns how much additional flow its chosen branch can deliver. limit is the smallest residual capacity encountered so far. At t it returns that bottleneck. Unwinding subtracts pushed from each selected forward residual arc and adds it to that arc’s reverse. An unsuccessful branch returns zero; another neighbor can then be tried. The same operation is valid when a chosen residual arc is itself a reverse arc.

3. 3. See cancellation in action

   Consider unit-capacity edges s→a, s→b, a→b, a→t and b→t. DFS might first choose s→a→b→t. Both remaining obvious forward routes now look blocked. The next residual path s→b→a→t uses b→a to undo a→b. Final flow consists of s→a→t and s→b→t, value 2. Without reverse updates the program would incorrectly stop at 1. This is why greedily deleting used edges is not flow.

4. 4. Trace the sample and prove the loop

   For the displayed network, DFS may send 1 along 1→2→3→4, then 2 along 1→2→4, then 2 along 1→3→4. Total is 5. Each augmentation preserves edge bounds and conservation: every internal path vertex receives and sends the same extra amount. Value strictly increases. Once no residual path exists, residual reachability gives a cut of equal capacity, so a larger feasible value is impossible.

5. 5. Know when termination is a useful guarantee

   With integer capacities all residual values stay integers, and every successful augmentation adds at least one unit. Thus at most F augmentations occur, where F is the final maximum flow value. Large capacities written in few bits can make F enormous: this is a pseudo-polynomial bound. Arbitrary real capacities do not give the same bound, and irrational examples can fail to terminate under poor path choices. Prefer BFS-based Edmonds–Karp or Dinic for stronger guarantees.

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<char>seen;
ll dfs(int v,int t,ll limit){
    if(v==t){
        return limit;
    }
    seen[v]=true;
    for(int id:graph[v]){
        int u=edges[id].to;
        if(seen[u]||edges[id].cap==0){
            continue;
        }
        ll pushed=dfs(u,t,min(limit,edges[id].cap));
        if(pushed==0){
            continue;
        }
        edges[id].cap-=pushed;
        edges[id^1].cap+=pushed; // Cancel this decision later if needed.
        return pushed;
    }
    return 0;
}
ll maxFlow(int n,int s,int t){
    ll answer=0;
    for(;;){
        seen.assign(n+1,false); // A fresh search for each augmenting path.
        ll pushed=dfs(s,t,numeric_limits<ll>::max());
        if(!pushed){
            return answer;
        }
        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((V+E)(F+1)) time for this implementation, including clearing seen[] for each DFS and the final failed search; commonly stated O(EF) when E is at least proportional to relevant V. F is the integral maximum-flow value, not its bit length. O(V+E) memory includes paired edges and O(V) recursion depth. Use modest capacities (for example ≤100 on small graphs) for this teaching DFS variant.

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 two edges leaving source 1 have total capacity 5, an upper bound. Augmentations attain 5, so the flow is maximum.

Practical applications

Choose DFS Ford–Fulkerson for residual-graph intuition, small integral flows or a quick reference solver. If the graph is a unit bipartite assignment network, direct matching algorithms avoid unnecessary generality. Edmonds–Karp removes dependence on F from the polynomial bound; Dinic batches compatible shortest paths.

Check your understanding

What may a later augmenting path do with an earlier flow decision?

Put it into practice

Test a network where the first DFS path must later be rerouted.