Design and Analysis of Algorithms
Maximum Flow Problem
(Push Relabel Algorithm)
Dr. D. P. Acharjya
Professor, SCOPE
SJT Annex – 201 E
13/03/2024 Dr. D. P. Acharjya 1
Push Relabel Algorithm
Let G = (V, E) be a flow network with source s and
sink t. Let c(u, v) be the capacity of the edge (u, v)E.
Push-relabel algorithm works in a localized manner.
Rather than examining the entire residual network to find an
augmenting path, push-relabel algorithms work on one vertex
at a time.
Total inflow and outflow for every vertex except
source and sink in Ford-Fulkerson is set to 0 (lack of
warehouse). Push Relabel algorithm allows inflow to
exceed the outflow before reaching the final flow.
In final flow, the inflow and outflow is maintained.
13/03/2024 Dr. D. P. Acharjya 2
Continued …
It works just like water flow
in a stream from higher
height to lower height.
The push-relabel algorithm
works with the help of
residual graph.
Excess flow of a vertex, u, is
defined as:
If e(u) > 0, then it is called overflow.
13/03/2024 Dr. D. P. Acharjya 3
Algorithm
PUSH – RELABEL G = (V, E)
1. Initialize PREFLOW (G, s)
2. While there exists an applicable PUSH or RELABEL
operation
3. do select an PUSH or RELABELE operation
13/03/2024 Dr. D. P. Acharjya 4
PREFLOW Algorithm
PREFLOW (G, s)
1. For each vertex uV of G
2. do h[u] = 0 [h: Refers to height of a vertex]
3. e[u] = 0 [e: Refers to excess flow]
4. For each edge (u, v) E of G
5. do f(u, v) = 0
6. f (v, u) = 0
7. h[s] = |V| [Height of source = Total vertices]
8. For each vertex u Adj[s]
9. do f(s, u) = c(s, u)
10. f(u, s) = - c(s, u)
11. e[u] = c(s, u)
13/03/2024 Dr. D. P. Acharjya 5
RELABEL and PUSH Algorithm
RELABEL (u)
1. When e[u] > 0 and for all vV, (u, v)Ef and h[u] h[v]
2. h[u] = 1 + Min{h[v]: (u, v)Ef}
PUSH (u, v)
1. When e[u] > 0 and h[u] > h[v]
2. df (u, v) = Min{e[u], cf (u, v)}
3. If (u, v) E
4. f(u, v) = f(u, v) + df (u, v)
5. Else
6. f(v, u) = f(v, u) - df (u, v)
7. e[u] = e[u] - df (u, v)
8. e[v] = e[v] + df (u, v)
13/03/2024 Dr. D. P. Acharjya 6
Numerical Illustration
Compute the maximum flow in the
graph using push-relabel algorithm.
13/03/2024 Dr. D. P. Acharjya 7
Numerical Illustration
13/03/2024 Dr. D. P. Acharjya 8
Continued …
13/03/2024 Dr. D. P. Acharjya 9
Continued …
13/03/2024 Dr. D. P. Acharjya 10
Continued …
13/03/2024 Dr. D. P. Acharjya 11
Continued …
13/03/2024 Dr. D. P. Acharjya 12
Continued …
13/03/2024 Dr. D. P. Acharjya 13
Continued …
13/03/2024 Dr. D. P. Acharjya 14
Continued …
13/03/2024 Dr. D. P. Acharjya 15
Continued …
13/03/2024 Dr. D. P. Acharjya 16
Continued …
13/03/2024 Dr. D. P. Acharjya 17
Continued …
13/03/2024 Dr. D. P. Acharjya 18
Continued …
13/03/2024 Dr. D. P. Acharjya 19
Continued …
13/03/2024 Dr. D. P. Acharjya 20
Continued …
13/03/2024 Dr. D. P. Acharjya 21