University of Algiers 1

Benyouçef benkhedda

Graph Theor y
Maximum Flow Problem
Course intended for students in L2 Computer Science

Presented by
Dr. Chaouki BOUFENAR
Associate Professor
[Link]@[Link]

2024/2025
 Maximum Flow Problem (Ford and Fulkerson Algorithm)
The challenge lies in efficiently routing available tonnages through various transportation methods, such as ships, trucks,
wagons, pipelines, and transmission lines, to their designated destinations.

Transportation network (Flow network)

A simple oriented and weighted graph where each arc is weighted by a positive number called capacity: 𝑐(e)

This network includes:

 A vertex without predecessors called Source : S
 A vertex without successors called Sink: K

𝟑
A D SinK vertex
Source vertex
2 1 2 0

S 0 C 1 K
1 1
3 3

Capacity B 𝟑 E
 Maximum Flow Problem (Ford and Fulkerson Algorithm)
𝒄 𝒆 𝒇 𝒆
Flow
A flow 𝒇 in a flow network, associates to each edge e an amount 𝒇 𝒆 𝟑∶2
A B

Flow concervation rule (rule of Kirchoff)

Incoming flow is equal to outgoing flow for every vertex except S and K.
1
5 𝟑
A
1
Compatible Flow
For each 𝒆 the flow through it does not exceed its capacity : 0 ≤ 𝒇 𝒆 ≤ 𝒄 𝒆
𝟑∶𝟏
Example A D
0:0

S C K
1:0

B 𝟑∶𝟎 E
 Maximum Flow Problem (Ford and Fulkerson Algorithm)
Full Flow
A flow is full if for any path from the source to the sink there is at least one saturated arc: 𝒇 𝒆 = 𝒄 𝒆
Example 𝟑∶𝟏
A D
𝟑∶𝟏
A D
S K
A D
0:0

S C K

1:0
S C K
D
B 𝟑∶𝟎 E
A 1
S C K

1:0
0:0

S C K
B E

B E A
S C K
S C K
B E
E
 Maximum Flow Problem (Ford and Fulkerson Algorithm)
Problème de recherche du flot maximum
Consiste à trouver la quantité maximale de flot à acheminer de la source S au puits P en tenant compte des capacités de
transport et de la quantité disponible en S.

Augmenting path
A path for which the flow can be increased.
 Directed arcs 𝐶 + haven’t reached their limit
 Undirected arcs 𝐶 − have a significant flow (non-zero flow) passing through them
I𝑛𝑐𝑟𝑒𝑎𝑠𝑒 𝑣𝑎𝑙𝑢𝑒 𝑖𝑠 𝜀 =M𝑖𝑛 {𝑐 𝑒 − 𝑓 𝑒 } / 𝑒 ∈ 𝐶 + }; {𝑓 𝑒 } / 𝑒 ∈ 𝐶 −
Example
Augmenting path 1 Augmenting path 2

A D A D

S C K S C K
𝐶 += 𝑆, 𝐴 , 𝐴, 𝐶 , 𝐶, 𝐷 , 𝐷, 𝑃 𝐶−= 𝐷, 𝐶
𝜀 =M𝑖𝑛 2 − 1; 1 − 0; 2 − 1; 1 − 0 = 𝟏 𝜀 =M𝑖𝑛 2 − 1; 1 − 0; 1; 1 − 0 = 𝟏
 Maximum Flow Problem (Ford and Fulkerson Algorithm)
Principle of algorithm
Pass a compatible flow through the network (the most obvious is the null flow), then improve it until you get a full flow.

• Ford, L. R., Jr. ; Fulkerson, D. R. (1956), Maximal flow through a network,

Canadian Journal of Mathematics 8 : 399–404.
• L. R. Ford ; D. R. Fulkerson (1962). Flows in Networks
 Maximum Flow Problem (Ford and Fulkerson Algorithm)
Input : Flow network
Output: Full flow 𝒇
BEGING
0) Mark the vertex S ; 𝒇𝟎 = 0 (𝒇𝒌 : 𝒇𝒍𝒐𝒘 𝒂𝒕 𝒔𝒕𝒆𝒑 𝒌) ; 𝒌 = 0
1) 𝑪+ = ∅ ; 𝑪− = ∅ ; 𝑨 = 𝑆 ;
2) Let 𝐓 a set of merked vertices and x ∈ 𝐓
While we can mark vertices Do
if (y is a successor of x ) and (𝑓 x, y < 𝑐 x, y ) Then Mark the vertex y ; 𝐶 + ← 𝐶 + ∪ x, y ; 𝐓← 𝐓∪ 𝐲
if (y is a predecessor of x ) and (𝑓 x, y > 0) Then Mark the vertex y ; 𝐶 − ← 𝐶 − ∪ x, y ;𝐓← 𝐓∪ 𝐲
End
If K is marked Then
𝐶 ← 𝐶+ ∪ 𝐶− // augmenting path from S to K
𝜀 =M𝑖𝑛 {𝑐 𝑒 − 𝑓 𝑒 } / 𝑒 ∈ 𝐶 + }; {𝑓 𝑒 } / 𝑒 ∈ 𝐶 −
We define a new flow as follow:
𝑓 𝑘 𝑒 + 𝜀 𝑓𝑜𝑟 𝑒 ∈ 𝐶 +
𝑓 𝑘+1 𝑒 = ൞ 𝑓 𝑘 𝑢 − 𝜀 𝑓𝑜𝑟 𝑒 ∈ 𝐶 −
𝑓𝑘 𝑢 𝑓𝑜𝑟 𝑒 ∉ 𝐶
Clear marks except in S, and go to 1)
Else
Stop. The flow is maximum.
End
END
 Maximum Flow Problem (Ford and Fulkerson Algorithm)
Example We mark the vertex D, because it is the successor of A and 𝑓 𝐴, 𝐷 < 𝑐 𝐴, 𝐷
𝟑
A D
2 1 2 1
𝐶+ ← 𝐶+ ∪ A, D = 𝑆, 𝐴 , A, D ; 𝐓 = 𝑆, 𝑨, 𝑫

S 0 C 1 K We mark the vertex K, because it is the successor of D and 𝑓 𝐷, 𝐾 < 𝑐 𝐷, 𝐾

1 1 𝐶+ ← 𝐶+ ∪ 𝐷, 𝐾 = 𝑆, 𝐴 , A, D , 𝐷, 𝐾 ; 𝐓 = 𝑆, 𝑨, 𝑫, 𝑲
3 3
B E The vertex K has been marked, stop. We therfore obtain the augmenting path
𝟑
𝐶 = 𝐶 + ∪ 𝐶 − = 𝑆, 𝐴 , A, D , 𝐷, 𝐾
We mark the vertex S by +. + + + 𝟏∶𝟎
+
S 𝟐∶𝟎 𝟑∶𝟎 D
We put :𝐓 = 𝑆 ; 𝐶 + ∪ 𝐶 − = ∅ et 𝑓 𝑘 = 0 ; an initial flow ; k=0 A K
+ + We calculate 𝜀 =M𝑖𝑛 {2 − 0; 3 − 0; 1 − 0 = 𝟏
𝟑∶𝟎
A D
We enhance then the flow 𝒇0 to get a new flow𝒇1, adding the amount 𝜀 = 1
+ + to the flow of arcs of 𝐶 + .
0:0

S C K
1:0

+ +
𝟑∶𝟏
A D
B 𝟑∶𝟎 E + +

0:0
S C K

1:0
𝒇𝟎 = 𝟎
Iteration 1
We mark the vertex A, because it is the successor of S and 𝑓 𝑆, 𝐴 < 𝑐 𝑆, 𝐴 B E
𝟑∶𝟎
+
𝐶 ←𝐶 ∪ +
𝑆, A ; 𝐓 = 𝑆, 𝑨
𝒇𝟏 = 𝟏
 Maximum Flow Problem (Ford and Fulkerson Algorithm)
𝟑∶𝟏
A D
The vertex K was marked, stop. We therfore obtain the augmenting path 𝐶
+ = 𝐶 + ∪ 𝐶 − = 𝑆, 𝐴 , A, D , 𝐷, 𝐸 , 𝐸, 𝐾
S 0:0 C K

1:0
+ + + + +
𝟐∶𝟏 𝟑∶𝟏 𝟏∶𝟎 E 𝟑: 𝟎
S A D K
B 𝟑∶𝟎 E
𝒇𝟏 = 𝟏 We calculate 𝜀 =M𝑖𝑛 {2 − 1; 3 − 1; 1 − 0; 3 − 0 = 𝟏
Clear marks except in S. We enhance then the flow 𝒇1 to get a new flow 𝒇2, adding the amount
𝜀 to the flow of arcs of 𝐶 + .
Iteration 2
We mark the vertex A , because it is the successor of S and 𝑓 𝑆, 𝐴
< 𝑐 𝑆, 𝐴 𝐶 + ← 𝐶 + ∪ 𝑆, A + +
; 𝐓 = 𝑆, 𝑨 A 𝟑∶𝟐
D
We mark the vertex D , because it is the successor of A and 𝑓 𝐴, 𝐷 < 𝑐 𝐴, 𝐷
+ +
+ +
; 𝐓 = 𝑆, 𝑨, 𝑫

0:0
𝐶 ←𝐶 ∪ A, D = 𝑆, 𝐴 , A, D S C k

1 :1
We mark the vertex E , because it is the successor of D and 𝑓 𝐷, 𝐸 < 𝑐 𝐷, 𝐸
+
𝐶+ ← 𝐶+ ∪ D, E = 𝑆, 𝐴 , A, D , D, E ; 𝐓 = 𝑆, 𝑨, 𝑫, 𝑬 B 𝟑∶𝟎 E
We mark the vertex P , because it is the successor of E and 𝑓 𝐸, 𝐾 < 𝑐 𝐸, 𝐾 𝒇𝟐 = 𝟐
𝐶+ ← 𝐶+ ∪ 𝑃 = 𝑆, 𝐴 , A, D , 𝐷, 𝐸 , 𝐸, 𝐾 ; 𝐓 = 𝑆, 𝑨, 𝑫, 𝑬, 𝑲
 Maximum Flow Problem (Ford and Fulkerson Algorithm)
𝟑∶𝟐
A D
The vertex K was marked, stop. We therfore obtain the augmenting path 𝐶
+ = 𝐶 + ∪ 𝐶 − = 𝑆, 𝐵 , B, C , C, E , E, 𝐾
0:0
S C K

1 :1
+ + + + +
𝟑∶0 𝟏∶𝟎 𝟏∶𝟎 E 𝟑: 𝟏
+ S B C P
B 𝟑∶𝟎 E
𝒇𝟐 = 𝟐 We calculate 𝜀 =M𝑖𝑛 {3 − 0; 1 − 0; 1 − 0; 3 − 1 = 𝟏
Clear marks except in S. We enhance then the flow 𝒇2 to get a new flow 𝒇3, adding the amount
𝜀 to the flow of arcs of 𝐶 + .
Iteration 3
We mark the vertex B , because it is the successor of S and 𝑓 𝑆, 𝐵 < 𝑐 𝑆, 𝐵
+ +
+
𝐶 ← 𝐶 ∪ 𝑆, B +
; 𝐓 = 𝑆, 𝐵 A 𝟑∶𝟐
D
We mark the vertex C , because it is the successor of B and 𝑓 𝐵, 𝐶 < 𝑐 𝐵, 𝐶
+ + +
+ +
; 𝐓 = 𝑆, 𝑩, 𝑪

0:0
𝐶 ←𝐶 ∪ B, 𝐶 = 𝑆, 𝐵 , B, 𝐶 S C K

1 :1
We mark the vertex E , because it is the successor of D and 𝑓 𝐶, 𝐸 < 𝑐 𝐶, 𝐸
+ +
+
𝐶 ←𝐶 ∪ +
D, E = 𝑆, 𝐵 , B, C , C, E ; 𝐓 = 𝑆, 𝑩, 𝑪, 𝑬 B 𝟑∶𝟎 E
We mark the vertex P , because it is the successor of E and 𝑓 𝐸, 𝐾 < 𝑐 𝐸, 𝐾 𝒇𝟑 = 𝟑
𝐶+ ← 𝐶+ ∪ 𝑃 = 𝑆, 𝐵 , B, C , C, E , E, 𝐾 ; 𝐓 = 𝑆, 𝑩, 𝑪, 𝑬, 𝑲
 Maximum Flow Problem (Ford and Fulkerson Algorithm)
𝟑∶𝟐
A D
The vertex K was marked, stop. We therfore obtain the augmenting
+ +
path 𝐶 = 𝐶 + ∪ 𝐶 − = 𝑆, 𝐵 , B, E , E, 𝐾
0:0
S C K

1 :1
+ + + +
+ + S 𝟑∶1 𝟑∶𝟎 𝟑: 𝟐
B E K
B 𝟑∶𝟎 E
𝒇𝟑 = 𝟑 We calculate 𝜀 =M𝑖𝑛 {3 − 1; 3 − 0; 1 − 0; 3 − 2 = 𝟏
Clear marks except in S. We enhance then the flow 𝒇3 to get a new flow𝒇4, adding the amount 𝜀 = 1
to the flow of arcs of 𝐶 + .
Iteration 3
We mark the vertex B , because it is the successor of S and 𝑓 𝑆, 𝐵 < 𝑐 𝑆, 𝐵
+ +
𝐶+ ← 𝐶+ ∪ 𝑆, B ; 𝐓 = 𝑆, 𝐵 A 𝟑∶𝟐
D
We mark the vertex E , because it is the successor of B and 𝑓 𝐵, 𝐸 < 𝑐 𝐵, 𝐸
+ +

0:0
+
𝐶 ←𝐶 ∪ +
D, E = 𝑆, 𝐵 , B, C , C, E ; 𝐓 = 𝑆, 𝑩, 𝑬 S C K

1 :1
We mark the vertex P , because it is the successor of E and 𝑓 𝐸, 𝐾 < 𝑐 𝐸, 𝐾
+ +
+
𝐶 ←𝐶 ∪ 𝑃 = +
𝑆, 𝐵 , B, E , E, 𝐾 ; 𝐓 = 𝑆, 𝑩, 𝑬, 𝑲 B 𝟑∶𝟏 E
𝒇𝟒 = 𝟒
 Maximum Flow Problem (Ford and Fulkerson Algorithm)
𝟑∶𝟐
A D
+

0:0
S C P

1 :1
B 𝟑∶𝟏 E
𝒇𝟒 = 𝟒
Clear marks except in S.
Iteration 5 𝟑∶𝟐
A D
We mark the vertex B , because it is the successor of S and 𝑓 𝑆, 𝐵 < 𝑐 𝑆, 𝐵
+
𝐶+ ← 𝐶+ ∪ 𝑆, B ; 𝐓 = 𝑆, 𝐵

0:0
S C K

1 :1
We mark the vertex E , because it is the successor of D and 𝑓 𝐶, 𝐸 < 𝑐 𝐶, 𝐸
+ +
+
𝐶 ←𝐶 ∪ +
D, E = 𝑆, 𝐵 , B, C , C, E ; 𝐓 = 𝑆, 𝑩, 𝑬 B 𝟑∶𝟏 E
𝒇𝟒 = 𝟒
The vertex K can’t be marked.

→ The flow 𝒇𝟒 = 𝟒 is maximum.