Network Flow
Sources and Sinks
07/17/25 CSE 373 AU 2005 -- Network 2
Flow
Flow Conservation
6
14
11
10 7
14 + 10 = 6 + 11 + 7
07/17/25 CSE 373 AU 2005 -- Network 3
Flow
Capacities/Saturation
7/9
S
7/10 7/7 T
7/11
flow / capacity
07/17/25 CSE 373 AU 2005 -- Network 4
Flow
Flow Cancellation
8
=
3
07/17/25 CSE 373 AU 2005 -- Network 5
Flow
Max Flow?
0/12
A B
0/20
0/16
0/4
S 0/10 0/7 T
0/9
0/13
0/4
C D
0/14
07/17/25 CSE 373 AU 2005 -- Network 6
Flow
A Flow
12/12
A B
19/20
11/16
1/4
S 0/10 7/7 T
0/9
12/13 4/4
C D
11/14
07/17/25 CSE 373 AU 2005 -- Network 7
Flow
A Flow
saturated 12 + 7 = 19 + 0
12/12
A B
19/20
11/16
1/4
S 0/10 7/7 T
0/9 saturated
12/13 4/4
saturated
C D
11/14
12 + 0 + 0 = 1 + 11
07/17/25 CSE 373 AU 2005 -- Network 8
Flow
Cuts
12/12
A B
19/20
11/16
1/4
S 0/10 7/7 T
0/9
12/13 4/4
C D
11/14
Remove edges until S is in one connected
23/29 component, and T in the other
07/17/25 CSE 373 AU 2005 -- Network 9
Flow
Cuts
12/12
A B
19/20
11/16
1/4
S 0/10 7/7 T
0/9
12/13 4/4
C D
11/14
Only count forward edges
23/26
07/17/25 CSE 373 AU 2005 -- Network 10
Flow
Cuts
12/12
A B
19/20
11/16
1/4
S 0/10 7/7 T
0/9
12/13 4/4
C D
11/14
23/31
07/17/25 CSE 373 AU 2005 -- Network 11
Flow
Min Cut
12/12
A B
19/20
11/16
1/4
S 0/10 7/7 T
0/9
12/13 4/4
C D
11/14
23/23
07/17/25 CSE 373 AU 2005 -- Network 12
Flow
Max Flow = Min Cut
12/12
A B
19/20
11/16
1/4
0/10
S
23 0/9
7/7 23 T
12/13 4/4
C D
11/14
No more capacity along cut to take more flow
07/17/25 CSE 373 AU 2005 -- Network 13
Flow
Ford-Fulkerson Method
• Single source, single sink
• Several algorithms are implementations of this
method
• Requires integer capacities for steady progress
• Fastest implementation computes max flow in
O(V^3) time
07/17/25 CSE 373 AU 2005 -- Network 14
Flow
Ford-Fulkerson Method
• Initialize flow f to 0
• While there exists an augmenting path p
– Augment flow f along p
• Return f
07/17/25 CSE 373 AU 2005 -- Network 15
Flow
An Augmenting Path
0/12
A B
0/20
0/16
0/4
S 0/10 0/7 T
0/9
0/13
0/4
C D
0/14
How much can be sent along the path?
07/17/25 CSE 373 AU 2005 -- Network 16
Flow
An Augmenting Path
bottleneck
12/12
A B
12/20
12/16
0/4
S 0/10 0/7 T
0/9
0/13
0/4
C D
0/14
Find a path with DFS or BFS.
07/17/25 CSE 373 AU 2005 -- Network 17
Flow
Another Augmenting Path
12/12
A B
12/20
12/16
0/4
S 0/10 0/7 T
0/9
0/13
0/4
C D
0/14
How much can be sent along the path?
07/17/25 CSE 373 AU 2005 -- Network 18
Flow
Another Augmenting Path
12/12
A B
bottleneck
12+4=16/20
12+4=16/16
0/4
S 4/10 4/7 T
0/9
0/13
0/4
C D
4/14
How much can be sent along the path?
07/17/25 CSE 373 AU 2005 -- Network 19
Flow
Residual
4/12
Graphs
A B
4/16 0/20
0/4
S 0/10 0/7 T
4/9
0/13 4/4
C D
4/14
12-4=8
A B
4
16-4=12 20
4 4
S 10 4 7 T
9-4=5
13 4
4
07/17/25
C CSE 373 14-4=10
AU 2005 -- Network
D 20
Flow
How much more flow can be sent?
A 4/12 B
Residual Graphs 4/16
0/4
0/20
S 0/10 0/7 T
8 4/9
A B
4 0/13 4/4
12 20 C D
4/14
4 4
S 10 4 7 T
5
13 4
A 4/12 B
4
C D 4/16 4/20
10
0/4
S 0/10 0/7 T
0/9
8
A B 4/13 4/4
4
12 C D
16 4/14
4
4 4
S 10 7 T
9
9 4 4 Can cancel out flow (BC)
07/17/25 CSE
4 373 AU 2005 -- Network 21
C Flow D
10
A 4/12 B
Residual Graphs 4/16
0/4
0/20
S 0/10 0/7 T
8 4/9
A B
4 0/13 4/4
12 12 C D
4 4/14
4 4
S 10 7 T
9
9 4 4
A 12/12 B
4
C D 12/16 12/20
10
0/4
S 0/10 0/7 T
0/9
A B 4/13 4/4
12
4 C D
8 4/14
12 12
4
S 10 7 T
9
9 4 4
07/17/25 CSE
4 373 AU 2005 -- Network 22
C Flow D
10
A 4/12 B
Residual Graphs 4/16
0/4
0/20
S 0/10 0/7 T
4/9
A B
12 0/13
4 4/4
8 C D
4/14
12 12
4
S 10 7 T
9
9 4 4
4 A 12/12 B
C D 12/16
10 19/20
0/4
S 0/10 7/7 T
0/9
A B 11/13 4/4
12
4 C D
1 11/14
12 19
4
S 10 7 T
9
2 11 4
07/17/25 CSE
11 373 AU 2005 -- Network 23
C Flow D
3
12/12 B
Residual Graphs 12/16
A
19/20
0/4
S 0/10 7/7 T
0/9
11/13 4/4
C D
11/14
A B
12
4 1
12 19
4
S 10 7 T
9
2 11 4
11
C D
3
No more augmenting paths: Max Flow!
Reachable vertices from source form one set, other vertices the other set.
Edges in the middle are the cut.
07/17/25 CSE 373 AU 2005 -- Network 24
Flow
Linear Programming: Max Flow
Variables:
SA, SB, AB, AT, BT
(amount of flow through the edge)
Constraints:
A • capacity
0/16 0/4 • 0 <= SA, SB, AB, AT, BT
• SA <= 16
S 0/10 T • SB <= 13
• AB <= 10
• AT <= 4
0/13 0/20 • BT <= 20
B • flow conservation
• AS = AB + AT
• AB + SB = BT
Objective:
max ( SA + SB + AB + AT + BT )
07/17/25 CSE 373 AU 2005 -- Network 25
Flow
Linear Programming: Min Cut
Variables:
SA, SB, AB, AT, BT (not cut = 0, cut = 1)
AinS, BinS (not in S = 0, in S = 1)
Constraints:
A • 0 <= SA, SB, AB, AT, BT
0/16 0/4
• 1 <= SA + AinS (A in S or SA is cut)
S 0/10 T • 1 <= SB + BinS (B in S or SB is cut)
0/13 • 0 <= AB - AinS + BinS
0/20
B (A in S but not B means AB is cut)
• 0 <= AT - AinS (A in S means AT is cut)
• 0 <= BT - BinS (B in S means BT is cut)
Objective:
min (16 SA + 4 AT + 10 AB + 13 SB + 20 BT)
07/17/25 CSE 373 AU 2005 -- Network 26
Flow
