Dinic’s Algorithm

Algorithm Description

Dinic’s algorithm is used to find the maximum flow in a flow network. It improves upon the Edmonds-Karp algorithm by using level graphs and blocking flows to achieve an O(V^2 * E) time complexity in typical cases, making it more efficient for dense networks.

C++ Code

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

#define V 6

struct Edge {
    int v;
    int flow;
    int capacity;
    int rev_index;
};

class Dinic {
    int n;
    vector<vector<Edge>> adj;
    vector<int> level;
    vector<int> ptr;

    bool bfs(int s, int t) {
        fill(level.begin(), level.end(), -1);
        queue<int> q;
        q.push(s);
        level[s] = 0;

        while (!q.empty()) {
            int u = q.front();
            q.pop();

            for (Edge &e : adj[u]) {
                if (level[e.v] < 0 && e.flow < e.capacity) {
                    level[e.v] = level[u] + 1;
                    q.push(e.v);
                }
            }
        }
        return level[t] >= 0;
    }

    int dfs(int u, int t, int flow) {
        if (u == t)
            return flow;

        for (int &i = ptr[u]; i < adj[u].size(); i++) {
            Edge &e = adj[u][i];
            if (level[e.v] == level[u] + 1 && e.flow < e.capacity) {
                int curr_flow = min(flow, e.capacity - e.flow);
                int temp_flow = dfs(e.v, t, curr_flow);

                if (temp_flow > 0) {
                    e.flow += temp_flow;
                    adj[e.v][e.rev_index].flow -= temp_flow;
                    return temp_flow;
                }
            }
        }
        return 0;
    }

public:
    Dinic(int n) : n(n), adj(n), level(n), ptr(n) {}

    void addEdge(int u, int v, int capacity) {
        Edge forward_edge = {v, 0, capacity, static_cast<int>(adj[v].size())};
        Edge backward_edge = {u, 0, 0, static_cast<int>(adj[u].size())};

        adj[u].push_back(forward_edge);
        adj[v].push_back(backward_edge);
    }

    int maxFlow(int s, int t) {
        if (s == t)
            return -1;

        int total_flow = 0;
        while (bfs(s, t)) {
            fill(ptr.begin(), ptr.end(), 0);
            while (int flow = dfs(s, t, INT_MAX))
                total_flow += flow;
        }
        return total_flow;
    }
};

int main() {
    Dinic dinic(V);

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

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

    return 0;
}

Time and Space Complexity

Operation	Time Complexity	Space Complexity
Initialization	O(V^2 * E)	O(V^2)
Dinic’s Algorithm	O(V^2 * E)	O(V^2)

Where:

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

← Back to Homepage