Push-Relabel Algorithm

Algorithm Description

The Push-Relabel algorithm is used to find the maximum flow in a flow network. It operates by pushing excess flow from nodes with higher potential (label) to nodes with lower potential, incrementally adjusting these labels until equilibrium is achieved, ensuring an efficient O(V^2 * sqrt(E)) time complexity in typical cases.

C++ Code

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

#define V 6

struct Edge {
    int to, capacity, flow, rev;
};

class PushRelabel {
    int n;
    vector<vector<Edge>> adj;
    vector<int> excess, height, count;
    queue<int> active;
    
    void push(int u, Edge &e) {
        int flow = min(excess[u], e.capacity - e.flow);
        e.flow += flow;
        adj[e.to][e.rev].flow -= flow;
        excess[u] -= flow;
        excess[e.to] += flow;
    }

    void relabel(int u) {
        int minHeight = INT_MAX;
        for (auto &e : adj[u]) {
            if (e.capacity - e.flow > 0) {
                minHeight = min(minHeight, height[e.to]);
                height[u] = minHeight + 1;
            }
        }
    }

    void discharge(int u) {
        while (excess[u] > 0) {
            if (count[u] < adj[u].size()) {
                Edge &e = adj[u][count[u]];
                if (e.capacity - e.flow > 0 && height[u] > height[e.to]) {
                    push(u, e);
                } else {
                    count[u]++;
                }
            } else {
                relabel(u);
                count[u] = 0;
            }
        }
    }

public:
    PushRelabel(int n) : n(n), adj(n), excess(n), height(n), count(n) {}

    void addEdge(int from, int to, int capacity) {
        adj[from].push_back({to, capacity, 0, (int)adj[to].size()});
        adj[to].push_back({from, 0, 0, (int)adj[from].size() - 1});
    }

    int maxFlow(int source, int sink) {
        height[source] = n;

        for (auto &e : adj[source]) {
            excess[source] += e.capacity;
            push(source, e);
        }

        while (!active.empty()) {
            int u = active.front();
            active.pop();
            discharge(u);
        }

        return excess[sink];
    }
};

int main() {
    PushRelabel pr(V);

    pr.addEdge(0, 1, 16);
    pr.addEdge(0, 2, 13);
    pr.addEdge(1, 2, 10);
    pr.addEdge(1, 3, 12);
    pr.addEdge(2, 1, 4);
    pr.addEdge(2, 4, 14);
    pr.addEdge(3, 2, 9);
    pr.addEdge(3, 5, 20);
    pr.addEdge(4, 3, 7);
    pr.addEdge(4, 5, 4);

    int source = 0;
    int sink = 5;
    cout << "The maximum possible flow is " << pr.maxFlow(source, sink);

    return 0;
}

Time and Space Complexity

Operation	Time Complexity	Space Complexity
Initialization	O(V^2 * E)	O(V^2)
Push-Relabel	O(V^2 * sqrt(E))	O(V^2)

Where:

• V: Number of vertices in the graph.
• E: Number of edges in the graph.

← Back to Homepage