Module 2 - Network Flow

Flow Networks, Networks with multiple sources and sinks, Floyd-

Warshall algorithm, Max Flow and Min Cut, Ford-Fulkerson Method
and Edmonds-Karp Algorithm, Bipartite Matching.

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Floyd-Warshall Algorithm

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Floyd-Warshall Algorithm
• All pair shortest path algorithm
• The All Pairs Shortest Path (APSP) calculates the shortest (weighted) path
between all pairs of nodes.
• Uses dynamic programming technique.
• It utilizes a directed weighted graph.
• Negative weights are allowed.
• Cycles with positive weights are permitted.

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Structure of a shortest path
• The Floyd-Warshall algorithm considers the intermediate vertices of
a shortest path.
• An intermediate vertex of a simple path p=<v1,v2,….,vl> is any vertex
in p other than v1 and vl.
• Intermediate vertex=<v2,v3,…,vl-1>
• The algorithm relies on the following observations,
• G be the graph with set of vertices V= {1,2,…,n}
• Consider a set of intermediate vertices for some value k. {1,2,…,k}
• For any pair of vertices i,j in V, consider all the paths from i to j whose
intermediate vertices are all drawn from {1,2,…,k} and the minimum weight
path is chosen among them.

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Structure of a shortest path (Contd…)
• The Floyd-Warshall algorithm exploits a relationship between path p and
shortest paths from i to j with all intermediate vertices in the set
{1,2,…,k}
• The relationship depends on whether k is an intermediate node or not.
• K is not an intermediate node
• Then all the intermediate nodes are in the set {1,2,…,k-1}
• This implies that the shortest path is present by utilizing any one of these intermediate nodes.
• This implies that, the shortest path is present in {1,2,…,k}
• K is an intermediate node
• The path is decomposed as i->k->j with p1 and p2.
• Both p1 and p2 are the shortest paths computed from the set of intermediate nodes {1,2,…,k-
1}

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Recursive Solution

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Example 1 – Find the minimal cost between
each pair of nodes.
2
1 2
6 7
3

3 4
1

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Initially create matrix D0

2
1 2 3 4
1 2
6 7
1 0 ∞ 3 ∞
3 2 2 0 ∞ ∞
𝐷0 = 3 ∞ 7 0 1
3 4
1 4 6 ∞ ∞ 0

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 D1[2,3] =min {D0[2,3], D0[2,1]+D0[1,3] }
= min {∞, 2+ 3}
Formulate D1 =5

1 2 3 4 D1[2,4] =min {D0[2,4], D0[2,1]+D0[1,4] }

= min {∞, 2+ ∞}
1 0 ∞ 3 ∞ =∞
2 2 0 ∞ ∞
𝐷0 = 3 ∞ 7 D1[3,2] =min {D0[3,2], D0[3,1]+D0[1,2] }
0 1 = min {7, ∞ + ∞}
4 6 ∞ ∞ 0 =7

D1[3,4] =min {D0[3,4], D0[3,1]+D0[1,4] }

1 2 3 4 = min {1, ∞ + ∞}
1 0 ∞ 3 ∞ =1

1 2 2 0 5 ∞
𝐷 =3 ∞ 7 0
D1[4,2] =min {D0[4,2], D0[4,1]+D0[1,2] }
1 = min {∞, 6+ ∞}
4 6 ∞ 9 0 =∞

D1[4,3] =min {D0[4,3], D0[4,1]+D0[1,3] }

= min {∞, 6+ 3}
Prepared By, Dr. Kovendan AKP., Assistant Professor Senior, =9
SCOPE, VIT, Vellore.
 D2[1,3] =min {D1[1,3], D1[1,2]+D1[2,3] }
= min {3, ∞ + 5}
Formulate D2 =3

1 2 3 4 D2[1,4] =min {D1[1,4], D1[1,2]+D1[2,4] }

= min {∞, ∞ + ∞}
1 0 ∞ 3 ∞ =∞
2 2 0 5 ∞
𝐷1 =3 ∞ 7 0 D2[3,1] =min {D1[3,1], D1[3,2]+D1[2,1] }
1 = min {∞, 7+2}
4 6 ∞ 9 0 =9

D2[3,4] =min {D1[3,4], D1[3,2]+D1[2,4] }

1 2 3 4 = min {1, 7+ ∞}
1 0 ∞ 3 ∞ =1
2 2 0 5 ∞
𝐷2 =3 9 7
D2[4,1] =min {D1[4,1], D1[4,2]+D1[2,1] }
0 1 = min {6, ∞ +2}
4 6 ∞ 9 0 =6

D2[4,3] =min {D1[4,3], D1[4,2]+D1[2,3] }

= min {9, ∞ + 5}
Prepared By, Dr. Kovendan AKP., Assistant Professor Senior, =9
SCOPE, VIT, Vellore.
 D3[1,2] =min {D2[1,2], D2[1,3]+D2[3,2] }
= min {∞, 3+ 7}
Formulate D3 = 10

D3[1,4] =min {D2[1,4], D2[1,3]+D2[3,4] }

1 2 3 4 = min {∞, 3+1}
1 0 ∞ 3 ∞ =4
2 2 0 5 ∞
𝐷2 = 9 7 D3[2,1] =min {D2[2,1], D2[2,3]+D2[3,1] }
3 0 1 = min {2, 5+9}
4 6 ∞ 9 0 =2

D3[2,4] =min {D2[2,4], D2[2,3]+D2[3,4] }

1 2 3 4 = min {∞, 5+1}
1 0 10 3 4 =6
2 2 0 5 6
𝐷3 = 9 7
D3[4,1] =min {D2[4,1], D2[4,3]+D2[3,1] }
3 0 1 = min {6, 9+9}
4 6 16 9 0 =6

D3[4,2] =min {D2[4,2], D2[4,3]+D2[3,2] }

= min {∞, 9+ 7}
Prepared By, Dr. Kovendan AKP., Assistant Professor Senior, = 16
SCOPE, VIT, Vellore.
 D4[1,2] =min {D3[1,2], D3[1,4]+D3[4,2] }
= min {10, 4+ 16}
Formulate D4 = 10

1 2 3 4 D4[1,3] =min {D3[1,3], D3[1,4]+D3[4,3] }

= min {3, 4+9}
1 0 10 3 4 =3
2 2 0 5 6
𝐷3 = 3 9 7 D4[2,1] =min {D3[2,1], D3[2,4]+D3[4,1] }
0 1 = min {2, 6+6}
4 6 16 9 0 =2

D4[2,3] =min {D3[2,3], D3[2,4]+D3[4,3] }

1 2 3 4 = min {5, 6+9}
1 0 10 3 4 =5
2 2 0 5 6
𝐷4 = 3 7 7
D4[3,1] =min {D3[3,1], D3[3,4]+D3[4,1] }
0 1 = min {9, 1+6}
4 6 16 9 0 =7

D4[3,2] =min {D3[3,2], D3[3,4]+D3[4,2] }

= min {7, 1+ 16}
Prepared By, Dr. Kovendan AKP., Assistant Professor Senior, =7
SCOPE, VIT, Vellore.
 2
1 2
Solution 6 7
3

3 4
1

0 10 3 4
2 0 5 6
𝐷4 = 7 7 0 1
6 16 9 0

Cannot find the path directly from this solution.

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Algorithm – Time Complexity Analysis

O(n3)

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Flow Networks

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Flow Network
• Directed graph G(V,E)
• Source – s
• Sink – t
• Edge (u,v) – Non negative
• Each edge has got a capacity c(u,v)
• Amount of traffic through the network edge.
• c(u,v) >=0
• No self loops allowed.
• If (u,v) is a edge that belongs to E, then the graph cannot contain an edge (v,u)
• Each vertex lies in some path from source to sink.
• s -> v -> t
• Each vertex other than s has at least one entering edge.
• |E| >= |V| - 1

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Example Flow Network

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Flow
• In a flow graph or flow network, the capacity is fixed.
• Flow is the actual amount passing through the network.
• Eg: Car passing through an edge.
• Flow representation
• Flow / Capacity
• Flow : Capacity

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Flow – Formal Definition
• Let G=(V,E) be a flow network with a capacity function c.
• A flow in G is a real valued function f: V x V -> R that satisfies two
properties,
1. Capacity Constraint
• For all (u,v) ∈ V, 0 ≤ f(u,v) ≤ c(u,v)
• Flow ≤ Capacity
2. Flow Conservation Law
• Total flow into a node is equal to
total flow out of the node.
• 𝑓 𝑖𝑛 𝑢 = 𝑣∈𝑉 𝑓(𝑣, 𝑢)
• 𝑓 𝑜𝑢𝑡 𝑢 = 𝑣∈𝑉 𝑓(𝑣, 𝑢)
• 𝑓 𝑖𝑛 𝑢 = 𝑓 𝑜𝑢𝑡 (𝑢)

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 Example Flow graph Conservation Law:

Node a: in= 1+1 = 2

2/2
a d out = 2
1/3 2/3
Node b: in=2
1/3 1/1
1/3 out = 2
S t

Flow Value:
1/2
2/2
b c
2/3 |f| = V(f) = fout(s)
= fin (t)
=3

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Test your understanding
Fill ? With appropriate flow values.
?/4
a d
3/4 ?/10

1/7 2/6
S ?/6 t

?/4
9/11
b c
10/15

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Test your understanding - Solution

4/4
a d
3/4 8/10

1/7 2/6
S 6/6 t

4/4
9/11
b c
10/15

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Other points to remember in flow graph
Rational Capacities
b b
3 5
Multiply every 9 10
2 3 capacity by 6

a d a 6 d
1

1 7 2 21
c c
3 2

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 Other points to remember in flow graph
Antiparallel Edges
4
Anti parallel edge – a’
Not Allowed b
9
b 5 9 10
9 10
a 6 d
a 6 d

2 21
c
2 21
c

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 Other points to remember in flow graph
Multiple Source and Sink

t1 t1
∞ s1 ∞
s1
Internal Internal
s ∞
Node t2 Node t2 t
∞
s2 s2 ∞
t3 t3

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
The Ford-Fulkerson method

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Residual Graph - Gf
• Gf consists of edges with capacities that represent how we can
change the flow on an edge of G.
• Gf may contain edges that are not in G.
• It only contains capacity.
• |Ef|<= 2|E|
• Given a flow f over G,

𝑐 𝑢, 𝑣 − 𝑓 𝑢, 𝑣 , 𝑖𝑓 (𝑢, 𝑣) ∈ 𝐸
𝑐𝑓 𝑢, 𝑣 = 𝑓 𝑣, 𝑢 , 𝑖𝑓(𝑣, 𝑢) ∈ 𝐸
0, 𝑂𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,
SCOPE, VIT, Vellore.
Residual Graph Example 1

b b
1 1
1/1 1

a d a 1 1 d
1/2

1 1
1 1/1 c
c

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Residual Graph Example 2

5/7
a d
3/3 5/8

2/2 1/1
S 1/1 t

2/3
4/5
b c
3/3

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Residual Graph Example 2 - Solution
5
a d
3 2
5
3
2 1 1
S t
1 1
4 2
b c
3

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Residual Graph
• Residual graph is not a flow graph as it violates the property of anti
parallel edges.

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Augmentations
• Augmentation is adding a path from source to sink in the residual
network.
• Its purpose is to increase the flow of the flow graph.
• If f is a flow in the flow graph and f’ is the flow in the residual network
we define f ↑ f’, the augmentation of flow f by f’, to be a function
from V x V to R defined by,

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 Flow graph a Residual graph
a 3
3
0/3
0/3
1 4 1
1/5 1/2 s b c t
1/1
s b c t 1 1
4 3
0/4 0/3
d e
d e 2
0/2

Path in Residual
Graph
a a Augment the Path in
3 C(P’)=min{3,3,1}=1 1/3 Flow Graph
3 1/3
1 4 1 1/5 2/2
s b c t 1/1
s b c t
1 1
4 3 0/4 0/3
d e d e
2 Prepared By, Dr. Kovendan AKP., Assistant Professor Senior, 0/2
SCOPE, VIT, Vellore.
Maximum Flow - The Ford-Fulkerson method
• We try to find out the max flow value of a graph.
• Max(V(f))

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Example Problem – Ford Fulkerson Method

a
0/3 Flow initialized to
0/3
Zero
0/1 0/5 0/2
s b c t

0/4 0/3
d e
0/2

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 Flow graph a Residual graph
a 3
3
0/3
0/3
1 5 2
0/5 0/2 s b c t
0/1
s b c t
4 3
0/4 0/3
d e
d e 2
0/2

Path in Residual
Graph
a Augment the Path in
a C(P’)=min{1,5,5}=1 0/3 Flow Graph
3 0/3
3
1/1 1/5 2/2
1 s b c t
5 2
s b c t
0/4 0/3
4 3
d e
d e Prepared By, Dr. Kovendan AKP., Assistant Professor Senior, 0/2
2 SCOPE, VIT, Vellore.
 Flow graph a Residual graph
a 3
3
0/3
0/3
1 4 1
1/5 1/2 s b c t
1/1
s b c t 1 1
4 3
0/4 0/3
d e
d e 2
0/2

Path in Residual
Graph
a a Augment the Path in
3 C(P’)=min{3,3,1}=1 1/3 Flow Graph
3 1/3
1 4 1 1/5 2/2
s b c t 1/1
s b c t
1 1
4 3 0/4 0/3
d e d e
2 Prepared By, Dr. Kovendan AKP., Assistant Professor Senior, 0/2
SCOPE, VIT, Vellore.
 a Flow graph a Residual graph
1/3 1 1
1/3 2 2

1/5 2/2 1 4
1/1 s b c t
s b c t
1 2
0/4 0/3 4 3

d e d e
0/2 2

Path in Residual
Graph
a a Augment the Path in
1 C(P’)=min{2,2,1,4,2,3}=1 2/3 Flow Graph
1 2/3
2 2
1 4 1/1 0/5 2/2
s b c t s b c t
1 2
4 3 1/4 1/3
d e d e
2 Prepared By, Dr. Kovendan AKP., Assistant Professor Senior, 1/2
SCOPE, VIT, Vellore.
 a Flow graph a Residual graph
2 2
2/3 1 1
2/3
0/5 2/2 1 5
1/1 s b c t
s b c t 2
1 1
3 2
1/4 1/3 1
d e d e
1/2 1

Path in Residual
Graph
a Final Flow graph
a
Not a valid path !!! 2/3 Maximum Flow
2 2 2/3
1 1 V(f)=3

1 1/1 0/5 2/2

5 s b c t
s b c 2 t

1 1 1/3
3 2 1/4
1
d e d e
1 Prepared By, Dr. Kovendan AKP., Assistant Professor Senior, 1/2
SCOPE, VIT, Vellore.
Homework
• Apply Ford Fulkerson method to find the maximum flow in the given
graph.

Question

Solution

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Cuts of flow network
• The Ford-Fulkerson method repeatedly augments the flow along
augmenting paths until it has found a maximum flow.
• How do we know that when the algorithm terminates, we have
actually found a maximum flow?
• The max-flow min-cut theorem, tells us that a flow is maximum if
and only if its residual network contains no augmenting path.

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Cut
• A cut (S,T) of flow network G =(V,E) is a partition of V into S and T such
that T= V – S and s ∈ S and t ∈ T.
• It consists of edges with one end point in S and the other end point in
T.
S
• This cut is referred as S-T cut. a
3
• Eg: S={s,a,c} T={b,d,e,t} 3

1 5 2
s b c t

4 3
d e T
2
Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,
SCOPE, VIT, Vellore.
 a S

Capacity of a Cut 3
3

1 5 2
s b c t
• The capacity of a S-T cut is denoted by C(S,T).
4 3
𝐶 𝑆, 𝑇 = 𝐶(𝑢, 𝑣) d e T
𝑢∈𝑆 2
𝑣∈𝑇
• Summation of capacity of outgoing edges from S to T.
• Eg: S={s,a,c} T={b,d,e,t}
Outgoing edges={(s,b),(c,t)}
C(S,T) = 1+2
C(S,T) = 3
• A min cut in a S-T cut is defined as a cut with minimum capacity.
Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,
SCOPE, VIT, Vellore.
Flow across the cut
• It is also referred to a the net flow.
• If f is the flow in the graph G, then the net flow f(S,T) across the cut
(S,T) is defined as follows,

• Summation of Flow of outward edge from S – Summation of Flow of

inward edge to S.

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Flow across the cut - Example
a S
1/3
1/3
f(S,T) = [f(s,b)+f(c,t)]-[f(b,c)]
1/1 1/5 2/2
= (1 + 2) – (1) s b c t

=2 0/4 0/3
d e T
0/2
f(v) = |f| = 2

f(S,T) = |f|

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Example 2
• Net flow

• Capacity

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Proof
• Let f be a flow in a flow network G with source s and sink t, and let
(S,T) be any cut of G. Then the net flow across (S,T) is f(S,T) = |f|.

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,
SCOPE, VIT, Vellore.
Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,
SCOPE, VIT, Vellore.
Max Flow Min Cut Theorem

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,
SCOPE, VIT, Vellore.
Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,
SCOPE, VIT, Vellore.
The basic Ford-Fulkerson algorithm

O(E .|f*|)

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Find the maximum flow for the given flow
graph using Ford Fulkerson algorithm.
0/4
a d
0/10 0/10

0/8
0/2 0/6
S t

0/10
0/10
b c
0/9

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,
SCOPE, VIT, Vellore.
Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,
SCOPE, VIT, Vellore.
Homework
• Find the maximum flow for the given flow graph using Ford Fulkerson
algorithm.

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Edmond-Karp

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Edmond-Karp
• It is a special implementation case of Ford Fulkerson Algorithm.
• Ford Fulkerson Algorithm does not mention how to find the augmented
path.
• So, It leads to a time complexity of O(E.|f*|)
• The time complexity depends on the capacity value of the edge.
• This negativity of Ford Fulkerson Algorithm is rectified in Edmond
Karp.

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Edmond Karp
• It uses breadth first search (BFS) to find the augmenting paths.
• The BFS technique provides the shortest augmenting path every time
there by reducing the time complexity to O(V.E2)
• The time complexity of Edmond karp no longer depends on the
capacity value of the edge.
• Hence, this algorithm falls under the category of Strong Polynomial
Algorithm.

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Algorithm
Step 1: Begin
Step 2: Initialize the flow graph with flow values f as 0.
Step 3: While there exists a shortest augmenting path p in the residual
network Gf do,
Step 3.1: Augment p with f.
Step 4: Print the maximum flow value.
Step 5: End.

Time Complexity: O(V.E2)

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Example 1

1
20 18 8

15 3
S 2 t

10
12
3

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Example 1

1
0/20 0/8
0/18
0/15 0/3
S 2 t

0/10
0/12
3

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 Flow graph Residual graph
1
1
0/20 0/8
0/18 20 8
18
0/15 0/3
S 2 t 15 3
S 2 t
0/10
10
0/12
3 12
3

Modified Flow graph - 1

Path:
1 1. S
2. S-1;S-2
8/20 8/8
0/18 3. S-2; S-1-2; S-1-t
0/15 0/3
S 2 t Path chosen is: S-1-t

0/10 Min{20,8} = 8
0/12
3
Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,
SCOPE, VIT, Vellore.
 Flow graph Residual graph
1 1
8/20 8/8 8
0/18 8
12 18
0/15 0/3 15
S 2 t 3
S 2 t

0/10 10
0/12 12
3 3

Modified Flow graph - 2

Path:
1 1. S
2. S-1;S-2
8/20 8/8
0/18 3. S-2; S-1-2;
3/15 3/3 4. S-1-2; S-2-t; S-2-3;
S 2 t
Path chosen is: S-2-t
0/10
0/12 Min{15,3} = 3
3
Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,
SCOPE, VIT, Vellore.
 Flow graph Residual graph
1
1
8/20 8/8 8
0/18 8
12 18
3/15 3/3
S 2 t 12 3
S 2 t
0/10 3
10
0/12
12
3
3

Modified Flow graph - 3 Path:

1. S
1 2. S-1;S-2
3. S-2; S-1-2;
8/20 8/8 4. S-1-2; S-2-3;
0/18
5. S-2-3; S-1-2-3;
13/15 3/3
S 2 t 6. S-1-2-3; S-2-3-t

10/10 Path chosen is: S-2-3-t

10/12
3 Min{12,10,12} = 10
Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,
SCOPE, VIT, Vellore.
 Flow graph Residual graph
1
1
8/20 8/8 8
0/18 8
12 18
13/15 3/3
S 2 t 2 3
S 2 t
10/10 13
10 10
10/12 2
3
3

Path:
Final Flow graph 1. S
1 2. S-1;S-2
3. S-2; S-1-2;
8/20 8/8 Maximum Flow = 21
0/18
No outgoing edges from 2.
13/15 3/3
S 2 t
So No path in Residual graph.
10/10 So Stop.
10/12
3
Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,
SCOPE, VIT, Vellore.
Comparison of Edmond Karp and Ford
Fulkerson Algorithm
100
1 3
100
100 1 Find the maximum flow for the given
graph using Edmond Karp Algorithm.
S 1 1 t

100 1
100
2 4
100

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Comparison of Edmond Karp and Ford
Fulkerson Algorithm
100
1 3
100
100 1 |f|=200

S 1 1 t Within 2 iterations the answer can

be achieved.
100 1
100
2 4
100

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 Comparison of Edmond Karp and Ford
Fulkerson Algorithm
100 100
1 3 1 3
100 100
100 1 100 1

S 1 1 t S 1 1 t

100 1 100 1
100 100
2 4 2 4
100 100

In Ford Fulkerson – The highlighted path can be

taken as the initial path. Which will take
multiple iterations to converge.

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Homework
• Find the maximum flow in the given flow graph by applying Edmond
karp algorithm.

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Push Re-label Algorithm

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Push Re-label Algorithm
• Used to calculate the maximum flow of a given flow graph.
• Source node has a height value=total [Link] initially.
• Sink node has a heigh value of 0 and a excess flow of 0 initially.
• Each intermediate node has 2 values,
• Height: initially assigned to 0.
• Excess flow: initially assigned to 0.
• Flow is possible from a node at a greater height to a node at a lower
height.
• Flow is possible in all valid edges of the residual graph.
• The law of conservation is temporarily suspended until the computation is
done.
• There is no compromise with the capacity of each node.
Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,
SCOPE, VIT, Vellore.
Operations
• Push Forward
• Excess_flow(v) = min{excess_flow(u) , (C(u,v)-f(u,v))}
• Push Backward
• Excess_flow(v) = min{excess_flow(u), f(v,u)}
• Re-label
• Increase the height by 1.

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Algorithm and Time Complexity Analysis
O(V2.E)
Step 1: Begin
Step 2: Initialize h(s)=total number of nodes. Initialize other node heights as 0 and
excess_flow as 0.
Step 3: Push the maximum capacity from s to all the nodes with a valid path.
Step 4: Find the node with maximum excess_flow value and set it as the active
node.
Step 5: If all the excess_flow values are zero, go to step 7.
Step 6: For the active node perform the following.
Step 6.1: Check if there is a possibility of flow from the active node to other nodes.
Step 6.1.1: If yes, then perform push forward or push backward operation satisfying the capacity of the link.
Step 6.1.2: If no, perform re-label operation and increase the active nodes height by 1.
Step 6.2: Go to 4.
Step 7: End
Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,
SCOPE, VIT, Vellore.
Example - 1
• Find the maximum flow of the given graph by using push relabel
algorithm.
a
5 4

s 6 t

8 5
b

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 h(a)=0
e(a)=0 Initialize the height of source node as follows,

a h(s)= Total [Link] nodes = 4

5 4

h(t)=0 Initialize the height and excess flow of other

h(s)=4 s 6 t nodes.
e(t)=0

8 5
h(a) = 0 ; e(a) = 0
b h(b) = 0 ; e(b) = 0
h(t) = 0 ; e(t) = 0
h(b)=0
e(b)=0

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 h(a)=0 h(a)=0
e(a)=0 e(a)=5

a a
5 4 5/5 4

h(t)=0 h(t)=0
h(s)=4 s t h(s)=4 s 6 t
6 e(t)=0 e(t)=0

8 8/8 5
5
b b

h(b)=0 h(b)=0
e(b)=0 e(b)=8

h(s) > 0 (greatest height) and as s is the source

node perform the following:

Push(s,a)=5 => e(a)=5

Push(s,b)=8 => e(b)=8

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 h(a)=0 h(a)=0
e(a)=5 e(a)=11

a a
5/5 4 5/5 4

h(t)=0 h(t)=0
h(s)=4 s 6 t h(s)=4 s 6/6 t
e(t)=0 e(t)=0

8/8 5 8/8 5
b b

h(b)=0 h(b)=1
e(b)=8 e(b)=2

Active Node: b (greatest excess value) Push(b,a) = 6 => e(a)=6+5 = 11

Neighbours : {s,a,t} => e(b)=2

Re-label Operation: h(b)=h(b)+1 = 1

h(b) > h(a) => so flow is possible.

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 h(a)=0 h(a)=1
e(a)=11 e(a)=7

a a
5/5 4 5/5 4/4

h(t)=0 h(t)=0
h(s)=4 s t h(s)=4 s 6/6 t
6/6 e(t)=0 e(t)=4

8/8 5 8/8 5
b b

h(b)=1 h(b)=1
e(b)=2 e(b)=2

Active Node: a (greatest height) Push(a,t) = 4 => e(t) = 4

Neighbours : {s,b,t} => e(a)=7

Relabel Operation: h(a)=h(a)+1=1

h(a) > h(t) => so flow is possible.

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 h(a)=1 h(a)=2
e(a)=7 e(a)=1

a a
5/5 4/4 5/5 4/4

h(t)=0 h(t)=0
h(s)=4 s 6/6 t h(s)=4 s 0/6 t
e(t)=4 e(t)=4

8/8 5 8/8 5
b b

h(b)=1 h(b)=1
e(b)=2 e(b)=8

Active Node: a Push(a,b) = 6 => e(b) = 2+6=8

Neighbours : {s,b,t} => e(a)=7-6 = 1

Relabel Operation: h(a)=h(a)+1=2

h(a) > h(b) => so flow is possible.

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 h(a)=2 h(a)=2
e(a)=1 e(a)=1

a a
5/5 4/4 5/5 4/4

h(t)=0 h(t)=0
h(s)=4 s 0/6 t h(s)=4 s 0/6 t
e(t)=4 e(t)=9

8/8 5 8/8 5/5

b b

h(b)=1 h(b)=1
e(b)=8 e(b)=3

Active Node: b Push(b,t) = 5 => e(t) = 4+5=9

Neighbours : {s,a,t} => e(b)=8-5 =3

h(b) > h(t) => so flow is possible.

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 h(a)=2 h(a)=2
e(a)=1 e(a)=1

a a
5/5 4/4 5/5 4/4

h(t)=0 h(t)=0
h(s)=4 s 0/6 t h(s)=4 s 0/6 t
e(t)=9 e(t)=9

8/8 5/5 8/8 5/5

b b

h(b)=1 h(b)=2
e(b)=3 e(b)=3

Active Node: b
Neighbours : {s,a,t}

Relabel Operation: h(b)=h(b)+1=2

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 h(a)=2 h(a)=2
e(a)=1 e(a)=4

a a
5/5 4/4 5/5 4/4

h(t)=0 h(t)=0
h(s)=4 s 0/6 t h(s)=4 s 3/6 t
e(t)=9 e(t)=9

8/8 5/5 8/8 5/5

b b

h(b)=2 h(b)=3
e(b)=3 e(b)=0

Active Node: b Push(b,a) = 3 => e(a)=1+3=4

Neighbours : {s,a,t} => e(b)=0

Relabel Operation: h(b)=h(b)+1=3

h(b)>h(a), So flow is possible.

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 h(a)=2 h(a)=3
e(a)=4 e(a)=4

a a
5/5 4/4 5/5 4/4

h(t)=0 h(t)=0
h(s)=4 s 3/6 t h(s)=4 s 3/6 t
e(t)=9 e(t)=9

8/8 5/5 8/8 5/5

b b

h(b)=3 h(b)=3
e(b)=0 e(b)=0

Active Node: a
Neighbours : {s,b,t}

Relabel Operation: h(a)=h(a)+1=3

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 h(a)=3 h(a)=4
e(a)=4 e(a)=1

a a
5/5 4/4 5/5 4/4

h(t)=0 h(t)=0
h(s)=4 s 3/6 t h(s)=4 s 0/6 t
e(t)=9 e(t)=9

8/8 5/5 8/8 5/5

b b

h(b)=3 h(b)=3
e(b)=0 e(b)=3

Active Node: a Push(a,b)=3 (As per residual path) => e(b)=0+3=3

Neighbours : {s,b,t} => e(a) = 4-3 = 1

Relabel Operation: h(a)=h(a)+1=4

h(a)>h(b), So flow is possible.

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 h(a)=4 h(a)=4
e(a)=1 e(a)=1

a a
5/5 4/4 5/5 4/4

h(t)=0 h(t)=0
h(s)=4 s 0/6 t h(s)=4 s 0/6 t
e(t)=9 e(t)=9

8/8 5/5 8/8 5/5

b b

h(b)=3 h(b)=4
e(b)=3 e(b)=3

Active Node: b
Neighbours : {s,a,t}

Relabel Operation: h(b)=h(b)+1=4

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 h(a)=4 h(a)=4
e(a)=1 e(a)=1

a a
5/5 4/4 5/5 4/4

h(t)=0 h(t)=0
h(s)=4 s 0/6 t h(s)=4 s 0/6 t
e(t)=9 e(t)=9

8/8 5/5 5/8 5/5

b b

h(b)=4 h(b)=5
e(b)=3 e(b)=0

Active Node: b Push(b,s) = 3 => e(b)=0

Neighbours : {s,a,t}

Relabel Operation: h(b)=h(b)+1=5

h(b)>h(s)

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 h(a)=4 h(a)=5
e(a)=1 e(a)=0

a a
5/5 4/4 4/5 4/4

h(t)=0 h(t)=0
h(s)=4 s 0/6 t h(s)=4 s 0/6 t
e(t)=9 e(t)=9

5/8 5/5 5/8 5/5

b b

h(b)=5 h(b)=5
e(b)=0 e(b)=0

Active Node: a Push(a,s) = 1 => e(a)=0

Neighbours : {s,b,t}

Relabel Operation: h(a)=h(a)+1=5

h(a)>h(s)

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 h(a)=5
e(a)=0

a
4/5 4/4
No excess in the intermediate
h(t)=0
h(s)=4 s 0/6 t nodes !!!
e(t)=9
So, Stop.
5/8 5/5
b

h(b)=5
e(b)=0

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Example - 2
• Find the maximum flow of the given graph by using push relable
algorithm.
15
a b
10 3

s 5 8 t

12 17
c d
6

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 h(a)=0 h(b)=0
e(a)=0 e(b)=0
15
a b
10 3

5 8 h(t)=0
h(s)=6 s t
e(t)=0
12 17
c d
6
h(c)=0 h(d)=0
e(c)=0 e(d)=0

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 h(a)=0 h(b)=0 h(a)=0 h(b)=0
e(a)=0 e(b)=0 e(a)=10 e(b)=0
15 15
a b a b
10 3 10/10 3

5 8 h(t)=0 h(t)=0
h(s)=6 s t h(s)=6 s 5 8 t
e(t)=0 e(t)=0
12 17 12/12 17
c d c d
6 6
h(c)=0 h(d)=0 h(c)=0 h(d)=0
e(c)=0 e(d)=0 e(c)=12 e(d)=0

h(s) > 0 (greatest height) and as s is the source

node perform the following:

Push(s,a)=10 => e(a)=10

Push(s,c)=12 => e(c)=12

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 h(b)=0 h(a)=0 h(b)=0
h(a)=0
e(b)=0 e(a)=10 e(b)=0
e(a)=10
15 15
a b a b
3 10/10 3
10/10
h(t)=0 5 8 h(t)=0
h(s)=6 5 8 h(s)=6 s t
s t e(t)=0
e(t)=0

17 12/12 17
12/12 c d
c d 6/6
6
h(c)=0 h(c)=1 h(d)=0
h(d)=0
e(c)=12 e(c)=6 e(d)=6
e(d)=0

Active Node: c (greatest excess value) Push(c,d) = 6 => e(d)=6

Neighbours : {s,a,d} => e(c)=12-6=6

Re-label Operation: h(c)=h(c)+1 = 1

h(c) > h(d) => so flow is possible.

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 h(a)=0 h(b)=0 h(a)=1 h(b)=0
e(a)=10 e(b)=0 e(a)=0 e(b)=10
15 10/15
a b a b
10/10 3 10/10 3
h(t)=0 5 8 h(t)=0
h(s)=6 s 5 8 t h(s)=6 s t
e(t)=0 e(t)=0

12/12 17 12/12 17
c d c d
6/6 6/6
h(c)=1 h(d)=0 h(c)=1 h(d)=0
e(c)=6 e(d)=6 e(c)=6 e(d)=6

Active Node: a (greatest excess value) Push(a,b) = 10 => e(b)=10

Neighbours : {s,c,b} => e(a)=10-10=0

Re-label Operation: h(a)=h(a)+1 = 1

h(a) > h(b) => so flow is possible.

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 h(a)=1 h(b)=0 h(a)=1 h(b)=1
e(a)=0 e(b)=10 e(a)=0 e(b)=2
10/15 10/15
a b a b
3 10/10 3
10/10
h(t)=0 5 8/8 h(t)=0
h(s)=6 s 5 8 t h(s)=6 s t
e(t)=0 e(t)=0

12/12 17 12/12 17
c d c d
6/6 6/6
h(c)=1 h(d)=0 h(c)=1 h(d)=0
e(c)=6 e(d)=6 e(c)=6 e(d)=14

Active Node: b (greatest excess value) Push(b,d) = 8 => e(d)=6+8=14

Neighbours : {a,d,t} => e(b)=10-8=2

Re-label Operation: h(b)=h(b)+1 = 1

h(b) > h(d) => so flow is possible.

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 h(a)=1 h(b)=1 h(a)=1 h(b)=1
e(a)=0 e(b)=2 e(a)=0 e(b)=2
10/15 10/15
a b a b
10/10 3 10/10 3

8/8 h(t)=0 5 8/8 h(t)=0

h(s)=6 s 5 t h(s)=6 s t
e(t)=0 e(t)=14

12/12 17 12/12 14/17

c d c d
6/6 6/6
h(c)=1 h(d)=0 h(c)=1 h(d)=1
e(c)=6 e(d)=14 e(c)=6 e(d)=0

Active Node: d (greatest excess value) Push(d,t) = 14 => e(t)=14

Neighbours : {b,c,t} => e(d)=0

Re-label Operation: h(d)=h(d)+1 = 1

h(d) > h(t) => so flow is possible.

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 h(a)=1 h(b)=1 h(a)=1 h(b)=1
e(a)=0 e(b)=2 e(a)=5 e(b)=2
10/15 10/15
a b a b
10/10 3 10/10 3

5 8/8 h(t)=0 5/5 8/8 h(t)=0

h(s)=6 s t h(s)=6 s t
e(t)=14 e(t)=14

12/12 14/17 12/12 14/17

c d c d
6/6 6/6
h(c)=1 h(d)=1 h(c)=2 h(d)=1
e(c)=6 e(d)=0 e(c)=1 e(d)=0

Active Node: c (greatest excess value) Push(c,a) = 5 => e(a)=5

Neighbours : {s,a,d} => e(c)=6-5=1

Re-label Operation: h(c)=h(c)+1 = 2

h(c) > h(a) => so flow is possible.

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 h(a)=1 h(b)=1 h(a)=2 h(b)=1
e(a)=5 e(b)=2 e(a)=0 e(b)=7
10/15 15/15
a b a b
10/10 3 10/10 3

8/8 h(t)=0 5/5 8/8 h(t)=0

h(s)=6 s 5/5 t h(s)=6 s t
e(t)=14 e(t)=14

12/12 14/17 12/12 14/17

c d c d
6/6 6/6
h(c)=2 h(d)=1 h(c)=2 h(d)=1
e(c)=1 e(d)=0 e(c)=1 e(d)=0

Active Node: a (greatest excess value) Push(a,b) = 5 => e(b)=2+5=7

Neighbours : {s,b,c} => e(a)=0

Re-label Operation: h(a)=h(a)+1 = 2

h(a) > h(b) => so flow is possible.

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 h(a)=2 h(b)=1 h(a)=2 h(b)=1
e(a)=0 e(b)=7 e(a)=0 e(b)=4
15/15 15/15
a b a b
10/10 3 10/10 3/3

8/8 h(t)=0 5/5 8/8 h(t)=0

h(s)=6 s 5/5 t h(s)=6 s t
e(t)=14 e(t)=17

12/12 14/17 12/12 14/17

c d c d
6/6 6/6
h(c)=2 h(d)=1 h(c)=2 h(d)=1
e(c)=1 e(d)=0 e(c)=1 e(d)=0

Active Node: b (greatest excess value) Push(b,t) = 3 => e(t)=14+3=17

Neighbours : {a,d,t} => e(b)=4

h(b) > h(t) => so flow is possible.

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 h(a)=2 h(b)=1 h(a)=2 h(b)=2
e(a)=0 e(b)=4 e(a)=4 e(b)=0
15/15 11/15
a b a b
10/10 3/3 10/10 3/3
h(t)=0 5/5 8/8 h(t)=0
h(s)=6 s 5/5 8/8 t h(s)=6 s t
e(t)=17 e(t)=17

12/12 14/17 12/12 14/17

c d c d
6/6 6/6
h(c)=2 h(d)=1 h(c)=2 h(d)=1
e(c)=1 e(d)=0 e(c)=1 e(d)=0

Active Node: b (greatest excess value) Push(b,a) = 4 => e(a)=4

Neighbours : {a,d,t} => e(b)=0

Re-label Operation: h(b)=h(b)+1=2

h(b) > h(t) => so flow is possible.

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 h(a)=2 h(b)=2 h(a)=3 h(b)=2
e(a)=4 e(b)=0 e(a)=0 e(b)=0
11/15 11/15
a b a b
3/3 10/10 3/3
10/10
h(t)=0 1/5 8/8 h(t)=0
h(s)=6 s 5/5 8/8 t h(s)=6 s t
e(t)=17 e(t)=17

12/12 14/17 12/12 14/17

c d c d
6/6 6/6
h(c)=2 h(d)=1 h(c)=2 h(d)=1
e(c)=1 e(d)=0 e(c)=5 e(d)=0

Active Node: a (greatest excess value) Push(a,c) = 4 => e(c)=1+4=5

Neighbours : {s,c,b} => e(a)=0

Re-label Operation: h(a)=h(a)+1=3

h(a) > h(c) => so flow is possible.

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 h(a)=3 h(b)=2 h(a)=3 h(b)=2
e(a)=0 e(b)=0 e(a)=0 e(b)=0
11/15 11/15
a b a b
10/10 3/3 10/10 3/3

8/8 h(t)=0 1/5 8/8 h(t)=0

h(s)=6 s 1/5 t h(s)=6 s t
e(t)=17 e(t)=17

12/12 14/17 12/12 14/17

c d c d
6/6 6/6
h(c)=2 h(d)=1 h(c)=3 h(d)=1
e(c)=5 e(d)=0 e(c)=5 e(d)=0

Active Node: c (greatest excess value)

Neighbours : {s,a,d}

Re-label Operation: h(c)=h(c)+1=3

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 h(a)=3 h(b)=2 h(a)=3 h(b)=2
e(a)=0 e(b)=0 e(a)=4 e(b)=0
11/15 11/15
a b a b
10/10 3/3 10/10 3/3

h(t)=0 5/5 8/8 h(t)=0

h(s)=6 s 1/5 8/8 t h(s)=6 s t
e(t)=17 e(t)=17

12/12 14/17 12/12 14/17

c d c d
6/6 6/6
h(c)=3 h(d)=1 h(c)=4 h(d)=1
e(c)=5 e(d)=0 e(c)=1 e(d)=0

Active Node: c (greatest excess value) Push(c,a)=4 => e(a)=4

Neighbours : {s,a,d} => e(c) = 1

Re-label Operation: h(c)=h(c)+1=4

h(c)>h(a), So flow is possible.

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 h(a)=3 h(b)=2 h(a)=4 h(b)=2
e(a)=4 e(b)=0 e(a)=4 e(b)=0
11/15 11/15
a b a b
3/3 10/10 3/3
10/10
h(t)=0 5/5 8/8 h(t)=0
h(s)=6 s 5/5 8/8 t h(s)=6 s t
e(t)=17 e(t)=17

12/12 14/17 12/12 14/17

c d c d
6/6 6/6
h(c)=4 h(d)=1 h(c)=4 h(d)=1
e(c)=1 e(d)=0 e(c)=1 e(d)=0

Active Node: a (greatest excess value)

Neighbours : {s,c,b}

Re-label Operation: h(a)=h(a)+1=4

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 h(a)=4 h(b)=2 h(a)=5 h(b)=2
e(a)=4 e(b)=0 e(a)=0 e(b)=0
11/15 11/15
a b a b
3/3 10/10 3/3
10/10
h(t)=0 1/5 8/8 h(t)=0
h(s)=6 s 5/5 8/8 t h(s)=6 s t
e(t)=17 e(t)=17

12/12 14/17 12/12 14/17

c d c d
6/6 6/6
h(c)=4 h(d)=1 h(c)=4 h(d)=1
e(c)=1 e(d)=0 e(c)=5 e(d)=0

Active Node: a (greatest excess value) Push(a,c)=4 => e(c)=1+4=5

Neighbours : {s,c,b} => e(a)=0

Re-label Operation: h(a)=h(a)+1=5

h(a)>h(c), so flow is possible.

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 h(a)=5 h(b)=2 h(a)=5 h(b)=2
e(a)=0 e(b)=0 e(a)=0 e(b)=0
11/15 11/15
a b a b
10/10 3/3 10/10 3/3

1/5 8/8 h(t)=0 8/8 h(t)=0

h(s)=6 s t h(s)=6 s 1/5 t
e(t)=17 e(t)=17

12/12 14/17 12/12 14/17

c d c d
6/6 6/6
h(c)=4 h(d)=1 h(c)=5 h(d)=1
e(c)=5 e(d)=0 e(c)=5 e(d)=0

Active Node: c (greatest excess value)

Neighbours : {s,a,d}

Re-label Operation: h(c)=h(c)+1=5

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 h(a)=5 h(b)=2 h(a)=5 h(b)=2
e(a)=0 e(b)=0 e(a)=4 e(b)=0
11/15 11/15
a b a b
10/10 3/3 10/10 3/3

8/8 h(t)=0 5/5 8/8 h(t)=0

h(s)=6 s 1/5 t h(s)=6 s t
e(t)=17 e(t)=17

12/12 14/17 12/12 14/17

c d c d
6/6 6/6
h(c)=5 h(d)=1 h(c)=6 h(d)=1
e(c)=5 e(d)=0 e(c)=1 e(d)=0

Active Node: c (greatest excess value) Push(c,a)=4 => e(a)=4

Neighbours : {s,a,d} => e(c)=1

Re-label Operation: h(c)=h(c)+1=6

h(c) > h(a), So, flow is possible.

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 h(a)=5 h(b)=2 h(a)=6 h(b)=2
e(a)=4 e(b)=0 e(a)=4 e(b)=0
11/15 11/15
a b a b
10/10 3/3 10/10 3/3

8/8 h(t)=0 5/5 8/8 h(t)=0

h(s)=6 s 5/5 t h(s)=6 s t
e(t)=17 e(t)=17

12/12 14/17 12/12 14/17

c d c d
6/6 6/6
h(c)=6 h(d)=1 h(c)=6 h(d)=1
e(c)=1 e(d)=0 e(c)=1 e(d)=0

Active Node: a (greatest excess value)

Neighbours : {s,c,b}

Re-label Operation: h(a)=h(a)+1=6

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 h(a)=6 h(b)=2 h(a)=7 h(b)=2
e(a)=4 e(b)=0 e(a)=0 e(b)=0
11/15 11/15
a b a b
10/10 3/3 6/10 3/3

5/5 8/8 h(t)=0 h(t)=0

h(s)=6 s t h(s)=6 s 5/5 8/8 t
e(t)=17 e(t)=17
12/12 14/17 12/12 14/17
c d c d
6/6 6/6
h(c)=6 h(d)=1 h(c)=6 h(d)=1
e(c)=1 e(d)=0 e(c)=1 e(d)=0

Active Node: a (greatest excess value) Push(a,s)=4 => e(a)=0

Neighbours : {s,c,b}

Re-label Operation: h(a)=h(a)+1=7

h(a)>h(s). So, Flow is possible.

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 h(a)=7 h(b)=2 h(a)=7 h(b)=2
e(a)=0 e(b)=0 e(a)=0 e(b)=0
11/15 11/15
a b a b
6/10 3/3 6/10 3/3

5/5 8/8 h(t)=0 8/8 h(t)=0

h(s)=6 s t h(s)=6 s 5/5 t
e(t)=17 e(t)=17
12/12 14/17 11/12 14/17
c d c d
6/6 6/6
h(c)=6 h(d)=1 h(c)=7 h(d)=1
e(c)=1 e(d)=0 e(c)=0 e(d)=0

Active Node: c (greatest excess value) Push(c,s)=1 => e(c)=0

Neighbours : {s,a,d}

Re-label Operation: h(c)=h(c)+1=7

h(c)>h(s). So, Flow is possible.

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 h(a)=7 h(b)=2
e(a)=0 e(b)=0
11/15
No excess in the intermediate nodes !!!
a b
6/10 3/3
So stop.
h(s)=6 5/5 8/8 h(t)=0
s t
e(t)=17
11/12 14/17
c d
6/6
h(c)=7 h(d)=1
e(c)=0 e(d)=0

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Homework
• Find the maximum flow of the given graph by applying Push- Relabel
Algorithm.
a
0/3
0/3

0/1 0/5 0/2

s b c t

0/4 0/3
d e
0/2

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
 Application of Max Flow to
maximum matching problem

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.
Application of Max Flow to maximum
matching problem
• Bipartite Matching
• Any 4 applications mentioned in the pdf

Prepared By, Dr. Kovendan AKP., Assistant Professor Senior,

SCOPE, VIT, Vellore.