Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Algorithm Procedure
4.
Outline of Dinic’s algorithm : 
5.
Illustration  
6.
Implementation
7.
C++
8.
Python
9.
Complexity
10.
Applications
11.
Frequently Asked Questions
11.1.
Which algorithm is used to solve a maximum flow problem? 
11.2.
Does Ford Fulkerson use BFS or DFS?
11.3.
What is the capacity of a cut?
11.4.
What is the minimum cut of a graph?
12.
Conclusion
Last Updated: Mar 27, 2024
Hard

Dinic’s algorithm for Maximum Flow

Author SHIVANGI MALL
0 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

Problems involving maximum flow are resolved using Dinic's approach. Finding an achievable "flow" across a single source, a single sink flow network that is also a max, is how maximum flow problems are defined. In computer science, these issues are known as optimization problems. n this article, the reader will learn about Dinic’s algorithm for Maximum Flow and describe an example using a diagram. And we will also implement this problem in different languages and  discuss the time Complexities.

Dinic’s algorithm for Maximum Flow

Problem Statement

Given a graph that depicts a flow network with capacity along every edge. Find the largest flow that is possible from source s to sink t given the two vertices of source s and sink t in the graph under the following restrictions:

  • The flow on the edge does not exceed the capacity of an edge.
  • Except for s and t, every vertex has an incoming flow that is equivalent to an outgoing flow.
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Algorithm Procedure

There are various phases to the algorithm. We build the layered network of the residual network of G for each step. Then, we add an arbitrary blocking flow to the present flow by locating it in the layered network.

Outline of Dinic’s algorithm : 

  • To label every level of the current flow graph, create a level graph by performing BFS from the source node.

 

  • Stop and return the maximum flow if the sink is never reached while constructing the level graph.
     
  • Perform several DFSs from the source node to the sink node until a blocking flow is reached, using only valid edges in the level graph that was built. Then, add the bottleneck values of all the augmenting pathways discovered to determine the maximum flow.

A flow is considered blocked if no additional flows can be communicated using the level graph, meaning that no other s-t paths exist where the path vertices have the current levels 0, 1, 2, etc. Blocking Flow is equivalent to the Greedy algorithm's greatest flow path.

Illustration  

Let's go over an example to learn how Dinic's algorithm functions precisely.

We will start with the initial residual graph.

Graph

Flow Total = 0

First Iteration: In the first iteration, BFS is used to assign levels to every node. We also examine the possibility of increased flow (or there is an s-t path in the residual graph).

Graph

 

Now, we use levels to discover blocked flow (which means every flow path should have levels as 0, 1, 2, or 3). Three flows are sent collectively. In contrast to Edmond Karp, where we send one flow at a time, this is where it is optimized.

4 units of flow on the path s, 1, 3, and t.

flow in 6 units along path s - 1 - 4 - t.

4 units of flow on the s, 2, 4, and T paths.

Total flow is equal to Total flow + 4 + 6 + 4 = 14.

The residual graph changes to the one below after one iteration.

Graph

Second Iteration: We use the BFS of the modified residual graph mentioned above to give all nodes new levels. We also examine the possibility of increased flow (or there is an s-t path in the residual graph).

 

Now, we use levels to discover blocked flow (which means every flow path should have levels as 0, 1, 2, 3, or 4). This time, we're only able to send one flow.

5 units of flow along the line S-2-4-3-T

Total flow = Total flow plus 5 to equal 19
 

Third iteration: BFS is run, and a level graph is produced. Additionally, we determine whether there is room for additional flow before moving on. This time, the residual graph contains no s-t paths. Hence the procedure is stopped.

Implementation

Dinic's algorithm is implemented  as follows in a different language:

C++

// C++ implementation of Dinic's Algorithm
#include <bits/stdc++.h>
using namespace std;

// A structure to represent an edge between
// two vertex
struct Edge {
     int v; // Vertex v (or "to" vertex)
           // of a directed edge u-v. "From"
           // vertex u can be obtained using
           // index in adjacent array.

     int flow; // flow of data in edge

     int C; // capacity

     int rev; // To store index of reverse
              // edge in adjacency list so that
              // we can quickly find it.
};

// Residual Graph
class Graph {
      
      int V; // to represent number of vertexes
      int* level; // to stores level of a node
      vector<Edge>* adj;

public:
      Graph(int V)
      {
           adj = new vector<Edge>[V];
           this->V = V;
           level = new int[V];
      }


      // for adding an edge
      void addEdge(int a, int b, int C)
      {
           // for Forward edge
           Edge u{ b, 0, C, (int)adj[v].size() };

            // Back edge 
           Edge v{ a, 0, 0, (int)adj[u].size() };

           adj[u].push_back(u);
           adj[v].push_back(v); // reverse edge is represented
        }

        bool BFS(int s, int t);
        int sendFlow(int u, int sendflow, int t, int vtr[]);
        int DinicMaxflow(int s, int t);
     };

     bool Graph::BFS(int s, int t)
     {
         for (int i = 0; i < V; i++)
         level[i] = -1;

         level[s] = 0; // Level of source vertex

         // Make a queue, add the source vertex to it, 
         //and mark it as visited.The level[] array also functions as a visited array.
         list<int> q;
         q.push_back(s);

         vector<Edge>::iterator j;
         while (!q.empty()) {
         // to get front item
         int u = q.front();           
         q.pop_front();
         //pop front element
         for (j = adj[u].begin(); j!= adj[u].end(); j++) {
             Edge& ed = *j;
             // to check if level[e.v]<0
              if (level[ed.v] < 0 && ed.flow < e.C) {
                    level[ed.v] = level[u] + 1;
                     // level of parent + 1 is the level of current vertex
                     q.push_back(ed.v);
               }
          }
        }
       // IF we can not reach the sink we
       // return false else true
       return level[t] < 0 ? false : true;
    }

     // after BFS has established that there may be a flow and created levels, a //DFS-based function to send flow. For    every time BFS is called, this //function is also called many times.
     // flow : parent function call send current flow
     // u : represent current vertex
     // t : represent Sink
    int Graph::sendFlow(int u, int flows, int t, int start[])
    {
          // Sink reached
          if (u == t)
          return flows;

          // to traverse all adjacent edges
          for (; start[u] < adj[u].size(); start[u]++) {
          //from adjacency list of u pick the nect edge
          Edge& ed = adj[u][start[u]];

          if (level[ed.v] == level[u] + 1 && ed.flows < e.C) {
          //from u to t represent minimum flow
          int curr_flow = min(flows, ed.C - e.flows);

          int temp_flow = sendFlow(ed.v, curr_flow, t, start);

          // flow is greater than zero
          if (temp_flow > 0) {
                // add flow to current edge
                ed.flow += temp_flow;

                // subtract flow from reverse edge
                // of current edge
                adj[ed.v][ed.rev].flow -= temp_flow;
                return temp_flow;
           }
         }
       }
      return 0;
     }

      // it returns maximum flow in graph
      int Graph::DinicMaxflow(int s, int t)
      {
         // Corner case
         if (s == t)
         return -1;

         int total = 0; // Initialize result

         // Augment the flow while there is the path
         // from source to sink
         while (BFS(s, t) == true) {
         // store how many edges are visited
         // from V { 0 to V }
        int* start = new int[V + 1]{ 0 };

         while (int flows = sendFlow(s, INT_MAX, t, start))
                 // we add path flow to overall flow
                 total += flows;
          }
        // return maximum flow
        return total;
      }


// Driver Code
int main()
{
Graph g(6);
g.addEdge(0, 1, 16);
g.addEdge(3, 5, 20);
g.addEdge(0, 2, 13);
g.addEdge(1, 2, 10);
g.addEdge(1, 3, 12);
g.addEdge(2, 1, 4);
g.addEdge(2, 4, 14);
g.addEdge(3, 2, 9);
g.addEdge(4, 3, 7);
g.addEdge(4, 5, 4);


// next exmp
/*g.addEdge(0, 1, 3 );
g.addEdge(0, 2, 7 ) ;
g.addEdge(1, 3, 9);
g.addEdge(1, 4, 9 );
g.addEdge(2, 1, 9 );
g.addEdge(2, 4, 9);
g.addEdge(2, 5, 4);
g.addEdge(3, 5, 3);
g.addEdge(4, 5, 7 );
g.addEdge(0, 4, 10);


// next exp
g.addEdge(0, 1, 10);
g.addEdge(0, 2, 10);
g.addEdge(1, 3, 4 );
g.addEdge(1, 4, 8 );
g.addEdge(1, 2, 2 );
g.addEdge(2, 4, 9 );
g.addEdge(4, 3, 6 );
g.addEdge(4, 5, 10 ); */

cout << "Maximum flow " << g.DinicMaxflow(0, 5);
return 0;
}


Also check out - Phases of Compiler

Python

class Edge:
    def __init__(self, v, flow, C, rev):
        self.v = v
        self.flow = flow
        self.C = C
        self.rev = rev
        
# Residual Graph
//to create class graph

class Graph:
     def __init__(self, Vertex):
         self.adj = [[] for i in range(Vertex)]
         self.V = V
         self.level = [0 for i in range(Vertex)]
    #for adding an edge
    def addEdge(self, u, v, C):

        # Forward edge
        p = Edge(v, 0, C, len(self.adj[v]))

        # represent back edge
        q = Edge(u, 0, 0, len(self.adj[u]))
        self.adj[u].append(p)
        self.adj[v].append(q)

    #from s to t it is used to find if more flow can be sent 
    # Also assigns levels to nodes
    def BFS(self, s, t):
        for i in range(self.V):
            self.level[i] = -1

        #represent source vertex level
            self.level[s] = 0

        # Make a queue, add the source vertex to it, and mark it as #visited. level[] array also functions as a visited array
         // to create empty queue
        q = []
        q.append(s)         // to append source vertex
        while q:
            u = q.pop(0)         // pop element from queue
            for i in range(len(self.adj[u])):    //to traverse self.adj[u] 
                e = self.adj[u][i]
                if self.level[e.v] < 0 and e.flow < e.C:
                    # represent Level of current vertex is
                    # level of parent + 1
                    self.level[e.v] = self.level[u]+1
                    q.append(e.v)
        return False if self.level[t] < 0 else True

# after BFS has established that there may be a flow and created levels, a #DFS-based function to send flow.
# flow: represent Current flow send by parent function call
# start[] : To keep track of the next edge to be explored
# start[i] stores count of edges explored
# from i
# u: Current vertex
# t: Sink

    def sendFlow(self, u, flow, t, start):
        # Sink reached
        if u == t:
             return flow

        # Traverse all adjacent edges one -by -one
        while start[u] < len(self.adj[u]):
            
            # from adjacency list of u pick the next edge
            e = self.adj[u][start[u]]
            if self.level[e.v] == self.level[u]+1 and e.flow < e.C:

                #from u to t find minimum flow
                curr_flow = min(flow, e.C-e.flow)
                temp_flow = self.sendFlow(e.v, curr_flow, t, start)

                # flow is greater than zero
                if temp_flow and temp_flow > 0:

                    # add flow to the current edge
                    e.flow += temp_flow

                    # subtract flow from reverse edge
                    # of the current edge
                    self.adj[e.v][e.rev].flow -= temp_flow
                    return temp_flow
             start[u] += 1

    # Returns maximum flow in a graph
    def DinicMaxflow(self, s, t):
        # Corner case
        if s == t:
            return -1
        # Initialize result
        total = 0

        # Untill there is a path from source to sink, increase the flow
        while self.BFS(s, t) == True:

            # store how many edges are visited
            start = [0 for i in range(self.V+1)]
            while True:
                flow = self.sendFlow(s, float('inf'), t, start)
                if not flow:
                    break

                # to overall flow we add path flow
                total += flow

        # return maximum flow
        return total

g = Graph(6)
g.addEdge(0, 1, 16)
g.addEdge(0, 2, 13)
g.addEdge(1, 2, 10)
g.addEdge(1, 3, 12)
g.addEdge(2, 1, 4)
g.addEdge(2, 4, 14)
g.addEdge(3, 2, 9)
g.addEdge(3, 5, 20)
g.addEdge(4, 3, 7)
g.addEdge(4, 5, 4)
print("Maximum flow is", g.DinicMaxflow(0, 5))

Complexity

Worst case time complexity: Θ(E * V * V)

Average case time complexity: Θ(E * V * V)

Best case time complexity: Θ(E * V * V)

Space complexity: Θ(E + V)

Applications

Optimizing transportation within the constraints of the traffic

In computer networks, increasing packet flow.

Frequently Asked Questions

Which algorithm is used to solve a maximum flow problem? 

In a network, the maximum practical flow between a source and a sink is calculated using the Ford-Fulkerson algorithm.

Does Ford Fulkerson use BFS or DFS?

Ford Fulkerson uses the DFS approach.

What is the capacity of a cut?

As an upper limit on the flow from the source to the sink, a cut's "capacity" is utilized.

What is the minimum cut of a graph?

In graph theory, a cut (a division of a graph's vertices into two disjoint subsets) that is minimal in some measure is known as a minimum cut or min-cut of a graph.

Conclusion

We covered Dinic’s algorithm for Maximum Flow in this article. We hope this article helps you to learn something new. And if you're interested in learning more, see our posts on Ansible Interview Questions Part 1Ansible Interview Questions Part 212 Best DevOps Tools To Get Acquainted With, and DevOps Interview Questions.

Visit our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more.! Feel free to upvote and share this article if it has been helpful for you.

 

Thankyou

 

Previous article
Count single node isolated sub-graphs in a disconnected graph
Next article
Identify Same Contacts in a List of Contacts
Live masterclass