Chapter 39: DSA Maximum Flow
DSA Maximum Flow – 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 multiple examples with numbers, and most importantly helping you understand why maximum flow is one of the most powerful, most beautiful, and most frequently asked graph topics in interviews and real-world applications.
What is Maximum Flow Problem?
Maximum Flow is a classic optimization problem on a flow network (a special kind of directed graph).
We have:
- A source vertex (usually called s or source)
- A sink vertex (usually called t or sink)
- Directed edges with capacity (how much flow can pass through that edge)
- Goal: find the maximum possible flow from source to sink without violating capacity constraints
In simple words:
Imagine you have a network of pipes. Water (flow) enters from one point (source) and leaves from another point (sink). Each pipe has a maximum amount of water it can carry (capacity). Maximum Flow = maximum amount of water you can push from source to sink at the same time.
Real-life examples where Maximum Flow is used
| Real-world situation | Source | Sink | Flow = ? | Edges = ? |
|---|---|---|---|---|
| Water / oil pipeline network | Water source | City / factory | Maximum water / oil delivered | Pipes with capacity |
| Transportation / logistics | Warehouse | Retail stores | Maximum goods that can be shipped | Roads / routes |
| Computer network bandwidth | Server | Client | Maximum data throughput | Links with bandwidth |
| Job assignment / matching | People | Jobs | Maximum assignments possible | Possible matches |
| Image segmentation (computer vision) | Foreground pixels | Background pixels | Separation with min cut | Pixel similarity |
| Airline seat allocation | Available seats | Passengers | Maximum passengers accommodated | Flight legs |
| Bipartite matching | Left set (e.g. workers) | Right set (e.g. tasks) | Maximum matching | Possible assignments |
Important Concepts in Flow Networks
| Term | Meaning / Explanation |
|---|---|
| Flow network | Directed graph with source, sink, and capacities |
| Capacity (c(u,v)) | Maximum flow allowed on edge u → v (≥ 0) |
| Flow (f(u,v)) | Actual flow currently going through edge u → v |
| 0 ≤ f(u,v) ≤ c(u,v) | |
| Residual capacity | How much more flow can be sent: c(u,v) − f(u,v) |
| Residual graph | Graph that shows remaining possible flow (forward & backward edges) |
| Augmenting path | Path from source to sink in residual graph with positive residual capacity |
| Maximum flow | Largest possible flow from s to t |
| Min-cut | Smallest total capacity of edges whose removal disconnects s from t |
Very important theorem (Max-Flow Min-Cut Theorem):
Maximum flow = Minimum cut
This is the fundamental reason why Ford-Fulkerson and Edmonds-Karp work.
The Main Algorithms for Maximum Flow
There are three classic algorithms you should know:
- Ford-Fulkerson Method (conceptual foundation)
- Edmonds-Karp Algorithm (BFS implementation of Ford-Fulkerson)
- Dinic’s Algorithm (faster in practice, very common in competitive coding)
Today we’ll focus on Edmonds-Karp — it is the one most frequently asked in interviews and the easiest to understand and implement correctly.
Edmonds-Karp Algorithm (BFS-based Ford-Fulkerson)
Core idea:
- Start with zero flow everywhere
- While there exists an augmenting path from source to sink in the residual graph:
- Find the minimum residual capacity along that path (bottleneck)
- Augment (increase) flow along that path by the bottleneck amount
- Update residual capacities (forward decreases, backward increases)
- When no more augmenting path exists → we have maximum flow
Key point: Edmonds-Karp uses BFS to find the shortest augmenting path → guarantees polynomial time O(V E²)
Classic Example – Step-by-step
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
|
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 = 0 everywhere residual = same as capacity
Iteration 1 Find augmenting path using BFS: s → A → C → t Bottleneck (min capacity) = 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
Total flow = 6
Iteration 2 BFS finds: 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
Total flow = 10
Iteration 3 BFS finds: s → B → t Bottleneck = min(5, 7-4=3) = 3
Augment by 3:
- s→B: flow=3, residual forward=2, backward=3
- B→t: flow=7, residual forward=0, backward=7
Total flow = 13
Iteration 4 No more path from s to t in residual graph → maximum flow = 13
Final flow values:
- s→A: 10
- s→B: 3
- A→B: 4
- A→C: 6
- B→t: 7
- C→t: 6
Edmonds-Karp Code (standard interview version)
|
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 63 |
from collections import deque, defaultdict def edmonds_karp(graph, source, sink): # graph[u][v] = capacity from u to v # we will modify residual capacities residual = defaultdict(lambda: defaultdict(int)) for u in graph: for v in graph[u]: residual[u][v] = graph[u][v] parent = {} # to store path max_flow = 0 while True: # 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 # Find bottleneck (min residual capacity in 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 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 |
Summary – Bellman-Ford vs Dijkstra vs Max Flow Context
| Algorithm | Edge weights | Negative cycle? | All-pairs? | Typical use |
|---|---|---|---|---|
| Dijkstra | Non-negative | No | No | Normal weighted shortest path |
| Bellman-Ford | Any | Detects | No | Negative weights possible |
| Edmonds-Karp | Capacities ≥ 0 | No | No | Maximum flow problems |
| Floyd-Warshall | Any | Detects | Yes | All-pairs shortest path |
Summary – Maximum Flow in one line each
- Finds maximum possible flow from source to sink in a flow network
- Uses residual graph and augmenting paths
- Edmonds-Karp (BFS version of Ford-Fulkerson) → O(V E²)
- Dinic’s algorithm → faster in practice (O(V² E))
- Max-flow = min-cut theorem is the theoretical foundation
- One of the top 10 most important graph algorithms in interviews
- Real-world use: transportation, network bandwidth, matching problems, image processing, etc.
Would you like to go deeper into maximum flow or related topics?
Very natural next steps:
- Ford-Fulkerson vs Edmonds-Karp – why BFS makes it polynomial
- Step-by-step dry run of max flow with residual graph changes
- Min-cut – how to find the actual cut after max flow
- Maximum bipartite matching using max flow
- Dinic’s algorithm (faster version – 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! 😊
