Dinic’s algorithm or Dinitz’s algorithm is a strongly polynomial algorithm for computing the maximum flow in a flow network, conceived in 1970 by Israeli (formerly Soviet) computer scientist Yefim (Chaim) A. Dinitz.[1] The algorithm runs in 
Hello and welcome my name is William and today we’re still talking about network flow and in particular we’re looking at finding the maximum flow and a new very efficient method of solving the unweighted bipartite matching problem Dinic’s algorithm is one of those extremely fast and revolutionary algorithms which really pushed the field of network flow forwards it was one if not the first algorithm to introduce a bunch of new concepts like building a level graph combining multiple graph traversal techniques together and the concept of a blocking flow all of which we’ll get into so what is the next algorithm it’s a fast a strongly polynomial maximum flow algorithm the fact that it’s strongly polynomial is important it means that the runtime doesn’t depend on the capacity values of the flow graph for which all we know could be varied large what’s remarkable about Dinic’s is that not only is it fast in practice for general graphs but it boasts performance on bipartite graphs running in a time complexity of Big O of square root V times E the importance of this cannot be overstated it makes it possible to handle bipartite graphs of a ridiculous size if you’re doing competitive programming Linux is the de facto standard algorithm to solve maximum flow algorithms
The algorithm was conceived in 69 by Yefim (Chaim) A. Dinitz and published in 1970 the algorithm was later modified slightly and popularized by Shimon Evan mispronouncing din it’s algorithm as Dinic’s algorithm
Let’s start by talking about the algorithm itself but first beginning with an analogy suppose you and a friend are planning to meet up at the coffee shop a few streets east of where you are you’ve never been to this coffee shop and you don’t exactly know where it is but you know it’s somewhere East so how would you get there with the information you have would it make sense to south what about Northwest the only sensible directions are east northeast and southeast this is because you know that those directions guarantee that you make a positive progress towards the coffee shop
This form of heuristic ensures that we continuously may progress towards whatever place of interest we desire to go so how can we apply this concept to solving the maximum flow in this analogy you are the source node and the coffee shop is the sink the main idea behind Dinic’s algorithm is to guide augmenting paths from the source to the sink using a level graph and in doing so greatly reducing the runtime the weight Denic’s determines what edges may progress towards the sink T and which do not is by building what’s called a level graph
The levels of a graph are those obtained by doing a breadth-first search from the source furthermore an edge is only part of the level graph if it makes progress towards the sink that is an edge must go from a node at level L to another node at level L plus one the requirement that edges must go from L to L plus 1 prunes backwards or what I call sideways edges those are all the gray edges in the slide so ask yourself if you’re trying to get from s to T as quickly as possible does it make sense to take the red edge going in the backwards direction on the slide no taking the red edge doesn’t bring you any closer to the sink so it should only be taken if a detour is required this is why backwards edges are omitted from the level graph the same thing can be said about edges which cut across sideways across the same level since no progress is made it’s also worth mentioning that residual edges can be made part of the level graph but they must have a remaining capacity greater than zero so that’s the level graph
The actual steps to executing Denic’s are as follows first construct a level graph by doing a breadth-first search from the source to label all the levels of the current flow graph then if the sink was never reached while building the level graph you know you can stop and return the value of the maximum flow then using only valid edges in the level graph do multiple depth-first searches from the source to the sink until a blocking flow is reached and sum over the bottleneck values of all augmenting paths calculate the maximum flow as you do this repeat steps 1 2 3 a blocking flow is when we cannot find any more paths from the source to the sink because too many edges in the level graph have been saturated this will all become clear with an example
Let’s use Dinic’s algorithm to find the maximum flow of this flow graph if this were a bipartite graph we would also be able to get a maximum matching as a result all right step one is to figure out which edges are part of the current level graph you don’t need to think of the level graph as a totally separate graph you can think of it rather as a subset of the edges so we start at the source and do a breadth-first search outwards the first layer includes all the red nodes then this is the second layer and so on until we reach the sink now if we focus on the edges which form the level graph we can see that they are all edges which go from L to L plus 1 and level and have a remaining capacity greater than zero step two of the algorithm is to find paths from s to T until a blocking flow is reached that is we cannot find any more paths through the level graph so we start at the source and do a depth first search on the edges of level graph until the sink is reached
We found our first augmenting path in the bottleneck value along this path is 5 since 5 is the smallest remaining capacity so update the flow values along the path by 5 if you inspect the graph the blocking flow has not yet been reached since there still exists paths from s to T start once again the source and do a depth-first search for words now we found another path this one has a bottleneck value of 15 so augment the flow along the path by 15 units
Now let’s try and find another path from s to T what happens now is that we get stuck performing the depth-first search there are no edges in the level graph with a remaining capacity greater than zero which can lead us to the sink so the blocking flow has been reached we just finished the first blocking flow iteration now we reset and rebuild the level graph this time it should look different because the remaining capacities of multiple edges has changed start the source expand outwards taking all edges with a remaining capacity greater than zero which in this case is only the middle edge leading us to the red node the top edge going outwards from the source is saturated and so is the one going downwards
We keep doing this and building the level graph layer by layer awesome so this is our new level graph you can see that this time we have one extra layer to play with let’s try and find a path from s to T once again we start at the source and probe forwards using only edges part of the level graph oops we have now reached a dead end in our depth-first search because we can no longer go forwards what we need to do is backtrack and keep going until we reach the sink
Perfect we made it to the sink the current path has a bottleneck value of 10 now augment the flow by 10 units and now if you inspect the flow graph you will notice that the blocking flow has once again been reached now no more flow can be pushed through the network when we build a level graph which means the algorithm terminates the maximum flow is the sum of all the ball neck values which if you recall were 5 15 and 10 for a maximum flow of 30 the maximum flow can also be calculated by looking at the flow values of the edges leading into the sink highlighted in red on this slide however one of the pitfalls of the current implementation of Linux algorithm at the moment is that it may encounter multiple dead ends during a depth-first search phase this is especially bad if the same dead end is taken multiple times during a blocking flow iteration to resolve this issue in his original paper Donets suggested cleaning the level graph and getting rid of all the dead ends before each blocking flow phase then later in 1975 Shimon Evan suggested pruning dead ends when backtracking during the depth-first search phase effectively getting rid of dead ends on the fly as the algorithm executes this trick greatly speeds up and simplifies the algorithm because that ends our only ever encountered once awesome so that’s basically everything you need to know about Dinic’s so let’s summarize everything that we’ve learned first we talked about the motivation behind Dinic’s and why having a guiding heuristic can greatly speed up our algorithm then we talked about the intuition and practicality behind having a level graph that directs edges towards the sink then we talked about the concept of a blocking flow which is achieved by doing multiple depth-first searches on the level graph until the graph is saturated afterwards we looked at the process of rebuilding the level graph and finding the blocking flow and doing this process repeatedly until no more augmenting paths exist and the maximum flow is found and lastly we talked about a critical optimization of Donets algorithm which is pruning dead ends so that we do not encounter them again
Similar Posts:
- Graph Theory Tutorial – Algorithms Course
- Artificial Intelligence Knowledge Graph forDynamic Networks: An IncrementalPartition Algorithm
- What is a Graph Database? What is it Used For?
- What Is Graph Analytics, and Why Is It Important?
- Parallel Heuristics for Balanced Graph Partitioning Based on Richness of Implicit Knowledge