Do you think IIT Guwahati certified course can help you in your career?
No
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.
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.
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.
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).
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.
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;
}
You can also try this code with Online C++ Compiler
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))
You can also try this code with Online Python Compiler
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.