Lecture 26.
Maximum Flow
Algorithms
Sungkyunkwan University
Hyunseung Choo
choo@[Link]
Superintelligence Laboratory Copyright 2000-2025 Superintelligence
[Link]
Laboratory
1/31
Max Flow Problem
𝑮 = 𝐺(𝑉, 𝐸)
𝒙𝑖𝑗 = flow on arc (𝑖, 𝑗)
𝒖𝑖𝑗 = capacity of flow in arc (𝑖, 𝑗)
𝒔 = source node
𝒕 = sink node
Maximize 𝒗 = σ𝒋 𝒙𝒔𝒋
Subject to: σ𝒋 𝒙𝒊𝒋 − σ𝒌 𝒙𝒌𝒊 = 𝟎 for each 𝒊 𝒔, 𝒕
𝟎 ≤ 𝒙𝒊𝒋 ≤ 𝒖𝒊𝒋 for all (𝒊, 𝒋) ∈ 𝑬
Superintelligence Laboratory [Link] 2/31
Maximum Flows
We refer to a flow 𝑥 as maximum if it is feasible and
maximizes 𝑣
Our objective in the max flow problem is to find a
maximum flow
1
10, 8 8,7
s 1,1
t
6, 5 10,6
2
A max flow problem
Capacities and a non-optimum flow
Superintelligence Laboratory [Link] 3/31
Feasibility Problem: Find a Feasible Flow
warehouses retailers
6 1
6 6
5 2
7 7
4 3
8 6
5 4
9 5
4 5
Is there a way of shipping from the warehouses to
the retailers to satisfy demand?
Superintelligence Laboratory [Link] 4/31
Transformation to a Max Flow Problem
warehouses retailers
6 1
6
6 6
5 5 2 6
4 7 77
s 4 3 t
6
5
8 6
5 4 4 5
9 5
4 5
There is a 1-1 correspondence with flows from s to t
with 24 units (why 24?) and feasible flows for the
transportation problem
Superintelligence Laboratory [Link] 5/31
Feasibility Problem: Find a Matching
persons tasks
1 5
2 6
3 7
4 8
Is there a way of assigning persons to tasks so that each
person is assigned a task, and each task has a person
assigned to it?
Superintelligence Laboratory [Link] 6/31
Transformation to a Max Flow Problem
persons tasks
1 5
1 1
1 2 6 1
s 1 1 t
3 7
1
1
4 8
Does the maximum flow from s to t have 4 units?
Superintelligence Laboratory [Link] 7/31
Residual Networks
1 8,7
10, 8
1,1 uij ,xij
s t i j
6, 5 10,6
2
1
2 1
rij = uij - xij
8 7
s 1 t i j
1 4
xij
5 6
2
Let rij denote the
The Residual Network G(x) residual capacity of
arc (i,j)
Superintelligence Laboratory [Link] 8/31
Augmenting Paths
An augmenting path is a path from s to t in the residual network
The residual capacity of the augmenting path P
d(P) = min{rij : (i,j) P}
To augment along P, send d(P) units of flow along each arc of the
path, then, modify x and the residual capacities appropriately
rij := rij - d(P) and rji := rji + d(P) for (i,j) P
1 1
2 1 2
8 7 8 8
s 1 t s 1 t
1 4 4
5 6 6 6
2 2
Superintelligence Laboratory [Link] 9/31
Ford-Fulkerson Max-Flow (1/16)
Begin
x := 0
create the residual network G(x)
while there is some directed path from s to t in G(x) do
begin
let P be a path from s to t in G(x)
:= d(P)
send units of flow along P
update the r's
end
End {the flow x is now maximum}
Superintelligence Laboratory [Link] 10/31
Ford-Fulkerson Max-Flow (2/16)
4
2 5
3 1 1 1
2 2
s 4 t
3 1 2
This is the original network, plus reversals of the arcs
Superintelligence Laboratory [Link] 11/31
Ford-Fulkerson Max-Flow (3/16)
4
2 5
3 1 1 1
2 2
s 4 t
3 1 2
3
This is the original network, and
the original residual network
Superintelligence Laboratory [Link] 12/31
Ford-Fulkerson Max-Flow (4/16)
4
2 5
3 1 1 1
2 2
s 4 t
3 2
1
Find any s-t path in G(x)
Superintelligence Laboratory [Link] 13/31
Ford-Fulkerson Max-Flow (5/16)
4
2 5
3 1 1 1
2 1
2
s 4 t
2 1
3 1 2
1 1
3
Determine residual capacity of the path
Send units of flow in the path
Update residual capacities
Superintelligence Laboratory [Link] 14/31
Ford-Fulkerson Max-Flow (6/16)
4
2 5
3 1 1 1
2 1
2
s 4 t
1
2
3 2
1
1
3
Find any s-t path
Superintelligence Laboratory [Link] 15/31
Ford-Fulkerson Max-Flow (7/16)
4
2 5
3 1 1 1
2
1 11
s 4 t
1 1
2
3 1 2
1
1
1 1
3
Determine the residual capacity of the path
Send units of flow in the path
Update residual capacities
Superintelligence Laboratory [Link] 16/31
Ford-Fulkerson Max-Flow (8/16)
4
2 5
3 1 1 1
2
1 11
s 4 1
t
1
2
3 2
1
1
1 1
3
Find any s-t path
Superintelligence Laboratory [Link] 17/31
Ford-Fulkerson Max-Flow (9/16)
4
2 5
3 1 1 1
1 11
s 2
1 4 1
2
t
32 1
1
1
3 1
Determine the residual capacity of the path
Send units of flow in the path
Update residual capacities
Superintelligence Laboratory [Link] 18/31
Ford-Fulkerson Max-Flow (10/16)
4
2 5
3 1 1 1
1
2 11
s 21 4 1
2
t
2
3 1
1
1
3 1
Find any s-t path
Superintelligence Laboratory [Link] 19/31
Ford-Fulkerson Max-Flow (11/16)
4
2 5
3 1 1 1
1
2 11
s 2 4 2 t
1 1
2 1
1
11
2
1 2
1
3
Determine the residual capacity of the path
Send units of flow in the path
Update residual capacities
Superintelligence Laboratory [Link] 20/31
Ford-Fulkerson Max-Flow (12/16)
4
2 5
3 1 1 1
1
2 11
s 21
4 1
2
t
1
2 1
12 2
1
3
Find any s-t path
Superintelligence Laboratory [Link] 21/31
Ford-Fulkerson Max-Flow (13/16)
4
3
2 1
5
2
3 1 1 1
1 1
s 4 t
1 21
2 1
2
1
2
1 2
1
3
Determine the residual capacity of the path
Send units of flow in the path
Update residual capacities
Superintelligence Laboratory [Link] 22/31
Ford-Fulkerson Max-Flow (14/16)
4
3
2 5
1
23 1 1 1
1 1
s 21
4 1
2
t
1
2 1
2
1 2
1
3
There is no s-t path in the residual network
This flow is optimal
Superintelligence Laboratory [Link] 23/31
Ford-Fulkerson Max-Flow (15/16)
4
3
2 1
5
3
2 1 1 1
1 1
s 1
2 4 1
2 t
1
2
1
2
1 2
1
3
These are the nodes that are reachable from node s
Superintelligence Laboratory [Link] 24/31
Ford-Fulkerson Max-Flow (16/16)
1
2 5
1 1
2 2
s 4 t
2 2
Here is the optimal flow
Superintelligence Laboratory [Link] 25/31
How Do We Know
When a Flow Is Optimal?
1 8,8
10, 9
s 1,1
t
6,6 10,7
2
METHOD
There is no augmenting path in the residual network
1 reachable
1 8
from s in G(x)
9
s 1 t
3 not reachable
6
2
7 from s in G(x)
Superintelligence Laboratory [Link] 26/31
A Simple and Very Bad Example
1
M M
s 1 t
M M
Superintelligence Laboratory [Link] 27/31
After 1 Augmentation
1
M-1 M
1
s 1 t
M M-1
1
2
Superintelligence Laboratory [Link] 28/31
After Two Augmentations
1
M-1 M-1
1 1
s 1 t
M-1 M-1
1 1
2
Superintelligence Laboratory [Link] 29/31
After Three Augmentations
1
M-2 M-1
2 1
s 1 t
M-1 M-2
1 2
2
And so on
Superintelligence Laboratory [Link] 30/31
After 2M Augmentations
1
M M
s 1 t
M M
Superintelligence Laboratory [Link] 31/31
Thanks to contributors
Mr. Phuoc-Nguyen Bui (2024-2025)
Mr. Pham Van Nguyen (2022-2025)
Dr. Thien-Binh Dang (2017-2022)
Prof. Hyunseung Choo (2001-2025)
Superintelligence Laboratory Copyright 2000-2025 Superintelligence
[Link] Laboratory
32/31