Chapter 40: DSA Ford-Fulkerson Algorithm
DSA Ford-Fulkerson Algorithm – Let’s understand this topic properly and in depth, like I’m sitting next to you with a whiteboard, drawing the network step by step, explaining every single concept slowly and clearly, showing exactly how the flow changes in each iteration, and most importantly helping you understand why this algorithm is so beautiful, why it’s considered the foundation of maximum flow, and why interviewers love asking it.
What is the Ford-Fulkerson Algorithm?
The Ford-Fulkerson algorithm is a method to compute the maximum flow in a flow network.
It is not a single fixed algorithm with one implementation — it is a general strategy that says:
As long as there is a path from source to sink in the residual graph with positive capacity, keep sending flow along that path (augmenting path), and update the residual capacities. When no such path remains → you have found the maximum flow.
The name comes from Lester R. Ford Jr. and Delbert R. Fulkerson, who published the method in 1956.
Core Idea – Very Simple Intuition
Imagine water is flowing from a source (like a lake) to a sink (like a city) through a network of pipes.
Each pipe has a maximum capacity (how much water it can carry at once).
The Ford-Fulkerson idea is very greedy and powerful:
- Find any path from source to sink where every pipe still has some remaining capacity.
- Send as much water as possible along that path (limited by the bottleneck — the pipe with smallest remaining capacity on the path).
- Update the remaining capacity of each pipe on the path:
- Forward direction → reduce by the amount sent
- Backward direction → increase by the amount sent (this allows “undoing” flow later if needed)
- Repeat until no path with positive capacity remains from source to sink.
When you can’t send any more water → you have reached the maximum flow.
Very Important Concepts You Must Understand
- Residual Graph At any moment, the residual graph shows:
- How much more flow can be sent forward on each edge
- How much flow can be sent back (to cancel previous flow)
- Augmenting Path Any path from source to sink in the residual graph that has positive residual capacity on every edge.
- Bottleneck The minimum residual capacity along an augmenting path — this is how much extra flow we can send in this iteration.
- Max-Flow Min-Cut Theorem Maximum flow value = Minimum capacity of any s-t cut This is why Ford-Fulkerson always gives the correct maximum flow.
Classic Example – Step-by-step Execution
Graph:
Vertices: s (source), A, B, C, t (sink)
Edges with capacities:
- s → A : 10
- s → B : 5
- A → B : 4
- A → C : 8
- B → C : 2
- B → t : 7
- C → t : 6
Visual:
|
0 1 2 3 4 5 6 7 8 9 10 11 |
10 4 s─────A─────B─────7─────t │ │ 2 8 │ ↓ ↓ C─────6─────t |
Initialize:
flow on every edge = 0 residual capacity = original capacity
Iteration 1 Find an augmenting path (any path with positive residual capacity): s → A → C → t Bottleneck = min(10, 8, 6) = 6
Augment flow by 6:
- s→A: flow = 6, residual forward = 4, backward = 6
- A→C: flow = 6, residual forward = 2, backward = 6
- C→t: flow = 6, residual forward = 0, backward = 6
Current max flow = 6
Iteration 2 Find next augmenting path: s → A → B → t Bottleneck = min(4, 4, 7) = 4
Augment by 4:
- s→A: flow = 10, residual forward = 0, backward = 10
- A→B: flow = 4, residual forward = 0, backward = 4
- B→t: flow = 4, residual forward = 3, backward = 4
Current max flow = 10
Iteration 3 Find next path: s → B → t Bottleneck = min(5, 3) = 3
Augment by 3:
- s→B: flow = 3, residual forward = 2, backward = 3
- B→t: flow = 7, residual forward = 0, backward = 7
Current max flow = 13
Iteration 4 Try to find another path from s to t in residual graph.
Possible paths:
- s → B → C → t → no (C→t residual = 0)
- s → A → … → A has no outgoing residual capacity
- No path left
Maximum flow = 13
Final flow values:
- s→A: 10
- s→B: 3
- A→B: 4
- A→C: 6
- B→t: 7
- C→t: 6
Total flow out of s = 10 + 3 = 13 Total flow into t = 7 + 6 = 13 → correct
Ford-Fulkerson Code (Edmonds-Karp version – BFS implementation)
This is the version most commonly asked in interviews (polynomial time).
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
from collections import deque, defaultdict def ford_fulkerson(graph, source, sink): # graph[u][v] = capacity from u to v residual = defaultdict(lambda: defaultdict(int)) for u in graph: for v in graph[u]: residual[u][v] = graph[u][v] parent = {} max_flow = 0 while True: # Use BFS to find augmenting path visited = set() queue = deque([source]) visited.add(source) parent.clear() parent[source] = -1 found = False while queue and not found: u = queue.popleft() for v in residual[u]: if v not in visited and residual[u][v] > 0: queue.append(v) parent[v] = u visited.add(v) if v == sink: found = True break if not found: break # no more augmenting path # Find bottleneck capacity along the path path_flow = float('inf') v = sink while v != source: u = parent[v] path_flow = min(path_flow, residual[u][v]) v = u # Update residual capacities along the path v = sink while v != source: u = parent[v] residual[u][v] -= path_flow residual[v][u] += path_flow # backward edge v = u max_flow += path_flow return max_flow |
Ford-Fulkerson vs Edmonds-Karp
| Ford-Fulkerson (general method) | Edmonds-Karp (specific implementation) |
|---|---|
| Any way to find augmenting path | Always uses BFS (shortest path) |
| May run in exponential time if bad paths chosen | Guaranteed polynomial time O(V E²) |
| Conceptual foundation | Practical implementation used in interviews |
Most interviews expect Edmonds-Karp (BFS version) because it has proven time complexity.
Summary – Ford-Fulkerson in one line each
- Method to compute maximum flow by repeatedly finding augmenting paths
- Uses residual graph and backward edges to allow flow cancellation
- Correctness comes from Max-Flow Min-Cut theorem
- Edmonds-Karp (BFS version) → O(V E²) time
- Handles any capacity values (positive integers usually)
- One of the most beautiful and most powerful graph algorithms
- Basis for many real-world problems: network flow, matching, transportation, etc.
Would you like to go deeper into Ford-Fulkerson / maximum flow?
Very natural next topics:
- Step-by-step dry run with residual graph changes (very detailed)
- How to find the actual min-cut after max flow
- Maximum bipartite matching using Ford-Fulkerson
- Why Edmonds-Karp is polynomial while basic Ford-Fulkerson may not be
- Dinic’s algorithm (faster in practice – very common in competitive coding)
- Multiple source / multiple sink max flow problems
Just tell me which direction you want to go next — I’ll explain it in the same detailed, step-by-step, human-teacher style with clear examples and visuals! 😊
