Dinics Algorithm In C++

In this guide, you will discover the Dinic's algorithm implemented in C++ along with its procedures, fundamental ideas, demonstration, benefits, and drawbacks.

What is the Dinic's Algorithm?

A graph algorithm known as Dinic's method is responsible for calculating the maximum flow within a flow network. In certain scenarios of flow networks, it offers a more efficient time complexity compared to the Ford-Fulkerson technique using the Edmonds-Karp variation.

Steps in the Algorithm:

• ✅ Initialization: Start with a zero flow during initialization.
• ✅ Build Level Graph: Using BFS, determine the shortest path between each node in the residual graph and the source to build a level graph.
• ✅ Find Blocking Flows: Use DFS (Depth-First Search) to look for augmenting pathways in the level graph. Repeat this until no more enhancing pathways are available.
• ✅ Update Flow: Using the augmenting pathways discovered in step 3, update the flow.
• ✅ Repeat steps 2-4 until no augmenting pathways are available, indicating that the maximum flow has been reached.

Key Concepts:

• ✅ Augmenting Paths: In the residual graph, an augmenting path is a path that allows for the pushing of additional flow from the source to the sink. Dinic's method uses BFS (Breadth-First Search) to find augmenting pathways.
• ✅ Blocking Flows: A blocking flow is an edge-disjoint augmented channel from the source to the sink. Dinic's method iteratively constructs a blocked flow, increasing the total flow from source to sink with each iteration.
• ✅ Flow networks: A flow network is a directed graph in which the maximum amount of flow that may pass through each edge is represented by its capacity. In the networks, the nodes are the source and the sink, and where flow is pushed from the source to the sink while respecting the capacities of the edges.
• ✅ Residual Graph: Dinic's method works using a residual graph, which is a graph that demonstrates how much capacity each edge in the original graph remains after some flow has passed through it.

Time Complexity:

For regular graphs, Dinic's algorithm has a time complexity of "O(V^2 E)"; for bipartite matching, it is "O(min(V^(2/3), E^(1/2)) E)", where V and E represent the quantities of vertices and edges. Thanks to its effectiveness, this method is particularly suitable for various types of flow networks.

Example:

Let's consider a scenario to demonstrate the Dinic's Algorithm in C++.

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <complex>
#define MAX_N 500
#define INF 987654321
using namespace std;
typedef long long lld;
struct Node
{
    vector<int> adj;
};
Node graf[MAX_N];
struct Edge
{
    int u, v, cap;
    int f;
};
vector<Edge> E;
int v, e;
int s, t;
int dist[MAX_N];
int upTo[MAX_N];
int idd = 0;
inline bool BFS()
{
    for (int q=1;q<=v;q++) dist[q] = -1;
    queue<int> bfs_queue;
    bfs_queue.push(s);
    dist[s] = 0;
    while (!bfs_queue.empty())
    {
        int xt = bfs_queue.front();
        bfs_queue.pop();
        for (int q=0;q<graf[xt].adj.size();q++)
        {
            int currID = graf[xt].adj[q];
            int xt1 = E[currID].v;
            if (dist[xt1] == -1 && E[currID].f < E[currID].cap)
            {
                bfs_queue.push(xt1);
                dist[xt1] = dist[xt] + 1;
            }
        }
    }
    return (dist[t] != -1);
}
inline int DFS(int x, int minCap)
{
    if (minCap == 0) return 0;
    if (x == t) return minCap;
    while (upTo[x] < graf[x].adj.size())
    {
        int currID = graf[x].adj[upTo[x]];
        int x1 = E[currID].v;
        if (dist[x1] != dist[x] + 1)
        {
            upTo[x]++;
            continue;
        }
        int aug = DFS(x1, min(minCap, E[currID].cap - E[currID].f));
        if (aug > 0)
        {
            E[currID].f += aug;
            if (currID&1) currID--; else currID++;
            E[currID].f -= aug;
            return aug;
        }
        upTo[x]++;
    }
    return 0;
}
inline int Dinic()
{
    int f = 0;
    while (true)
    {
        if (!BFS()) break;
        for (int i=1;i<=v;i++) upTo[i] = 0;
        while (true)
        {
            int currFlow = DFS(s, INF);
            if (currFlow == 0) break;
            f += currFlow;
        }
    }
    return f;
}
inline void addEdge(int u, int v, int cap)
{
    Edge E1, E2;
    E1.u = u, E1.v = v, E1.cap = cap, E1.f = 0;
    E2.u = v, E2.v = u, E2.cap = 0, E2.f = 0;
    graf[u].adj.push_back(idd++);
    E.push_back(E1);
    graf[v].adj.push_back(idd++);
    E.push_back(E2);
}
int main()
{
    v = 4, e = 5;
    s = 1, t = 4;
    addEdge(1, 2, 50);
    addEdge(1, 4, 30);
    addEdge(2, 4, 30);
    addEdge(2, 3, 40);
    addEdge(3, 4, 20);
    printf("%d\n",Dinic());
    return 0;
}

Output:

Advantages

• ✅ Dinic's algorithm is more efficient than Ford-Fulkerson's method in practice, especially for graphs with sparse capacities.
• ✅ It ensures that the shortest augmenting paths are considered first, leading to faster convergence.

Limitations

• ✅ Dinic's method assumes integral capacities on edges. A scaling strategy can be necessary for fractional capacity.
• ✅ It doesn't directly support negative edge weights. However, it can be extended to handle them with modifications.