Differences
Push Relabel algorithms work on one vertex at a time. It doesn't examine the entire residual network to find an augmented path. This means that the Push Relabel algorithm works in a more localized manner.
In Ford-Fulkerson, the net difference between the total outflow and inflow for every vertex (Except source and sink) is maintained at 0. In the Push-Relabel algorithm, the inflow can be more than the outflow before reaching the final flow. Also, In the final flow, the net difference is 0 for all except the source and sink.
Let's see the Problem Statement of the Push Relabel Algorithm.
Problem Statement
A graph is given. It represents a flow network where every edge has a capacity. Also, the two vertices in the graph are source 's' and sink 't.' We have to find the maximum possible flow from s to t. It should follow the following constraints.
- Flow on the edge doesn't exceed the given capacity of the edge.
- An incoming flow equals outgoing flow for every vertex except s and t.
Let's understand the Push Relabel Algorithm by taking real-world examples.
Consider a fluid flow problem. Assume the edges as water pipes and nodes as joints. The source is at the highest level. It sends water to all adjacent nodes. Once the node has excess water, it pushes water to a smaller height node. If water gets locally trapped at a vertex, the vertex is Relabeled, which means its height increases.
Push Relabel algorithm
Let’s discuss the approach of the push-relabel algorithm in detail.
We can do this with a valid preflow and labeling function.
The Push Relabel algorithm will start an initial preflow. It means some vertices already have access. The preflow will be handled and modified during the execution. This algorithm will pick a vertex with excess and then push the excess to neighbour vertices. This will repeat until all vertices, except the source and the sink, are free from excess. The preflow without excess is a valid flow. That makes the algorithm terminate with an actual flow.
The second thing we need is the help of another function called the labeling function or the height function. This function assigns each vertex an integer. The labelling is only valid if it is possible to increase the flow from u to v. Then, the height of v must be smaller than the height of u by one. However, it can be equal or even higher.
If a valid labelling function exists, then will not exists an augmented path from s to t in the residual graph.
We push some excess between the vertices and update the labels of it in each step. If the preflow and the labeling are valid after each step, then the algorithm determines that the preflow is a valid flow. We also have valid labelling; therefore, there doesn't exist a path in the residual graph. Hence the flow is the maximum flow.
Now, let's discuss the algorithm step by step.
Algorithm
- Initialize the graph with a preflow and the labelling or height function.
- Initialize each edge outgoing from s with its maximal capacity and all other edges with zero.
-
The two basic operations that we perform are described below.
- Push() on a vertex: We try to push as much excess flow from one vertex u to a neighboring vertex v.
- Relabel on a vertex: We will increase the vertex's height when we cannot push the excess to any adjacent vertex. Also, we can expand it by as much as possible while still maintaining the validity of the labeling.
- After that, when the preflow is a flow, we return it.
Let’s see the above algorithm in detail.
Initialize Preflow means initializing the flows and height of the vertices.
In this step, we will do the following initialization.
Initialize the height and flow of every vertex as 0.
Initialize the height of the source vertex equal to the total number of vertices in the graph.
Initialize the flow of every edge as 0.
Initially, flow and excess flow is equal to the capacity for all vertices adjacent to source s.
Push() Operation
It is used to make the flow from a node that has excess flow.
If a vertex has excess flow and has an adjacent with a smaller height (in the residual graph), then we push the flow from the vertex to the adjacent with a lower height. The amount of pushed flow through the pipe (edge) equals the edge's minimum excess flow and capacity.
Relabel() Operation
It is used when a vertex has excess flow, and none of its adjacent is at a lower height. This operation is used to increase the vertex's height to perform push() operations. We pick the minimum height adjacent in the residual graph and add 1 to it to increase height.
Check out this article for the example to understand it better and its implementation. Implementation of Push Relabel Algorithm.
Complexity Analysis
Time Complexity: There will be at most O(VE) saturating and O(V^2E) non-saturating pushes.
Saturating pushes means a push where the total capacity of an edge is used. Non-saturating pushes a push where the total capacity of an edge is partially used. If we find the next vertex with excess in O(1) time, then the overall time complexity of the algorithm is O(V^2E).
Also Read - Kadanes Algorithm
Frequently Asked Questions
What is Push Relabel Algorithm?
It is an algorithm to find the maximum flow of a flow network.
What was the reason behind naming it as Push Relabel Algorithm?
In the "Push Relabel Algorithm," Push, and Relabel are the two primary functions of this algorithm.
Who designed the Push Relabel Algorithm?
Andrew V. Goldberg and Robert Tarjan developed the Push Relabel Algorithm.
The Push Relabel Algorithm is the most efficient maximum flow algorithm. Why?
Push Relabel Algorithm requires O(V^2E) time complexity, which is asymptotically more efficient than the O(VE^2) Edmonds–Karp algorithm.
Who designed the concept of preflow and when?
Alexander V. Karzanov designed the concept of a preflow, published in 1974 in Soviet Mathematical Dokladi.
Conclusion
In this article, we have discussed Introduction to Push Relabel Algorithm. We have also addressed the problem statement with the algorithm. At last, we have seen their time complexity and some related FAQs.
After reading about the Introduction to Push Relabel Algorithm, are you not feeling excited to read/explore more articles on Data Structures and Algorithms? Don't worry; Coding Ninjas has you covered. See Graph, Binary Tree, BFS vs DFS, Check for Balanced Parentheses in an Expression, and Stack to learn.
Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, and many more!
Do upvote our blogs if you find them helpful and engaging!
Happy Learning!
117+ registered 