Dinic’s Algorithm
Dinic’s algorithm is a revolutionary graph algorithm. Dinic’s is an extremely effective way to calculate the maximum flow of a graph. His algorithm appears a lot in computer networking. Due to it being significantly faster than the other max flow algorithms,
What is a max flow problem?
Max flow problems are graph problems. A graph will have a source (start) and sink (end) nodes. The goal is to push as much “flow” from the source to the start. Each edge has a certain value, which is the current capacity or total capacity. For example, 4/17 means a total of 17 units of flow can be pushed through, but currently only 4 units are being used. These problems often deal with bottleneck values. The flow of a certain path is dictated by the smallest value. Max-flow problems can be visualized as water pipes. Water is being pushed through the system, and pipes restrict the amount of water that it is allowed to pass.
Dinic’s algorithm goes in a cycle until it is complete. The order of operations goes as follows:
Creating a level graph:
Level graph intuition (paraphrased from William Fiset Dinic’s algorithm video)
In this example, someone is trying to walk to a certain place. They are aware that the place is to the east. Given all eight directions, instructions don’t even need to be considered. Only the north-east, east, and south-east ever need to be considered. Going west only results in an increased distance from the target since they are walking away from the direction they were given.
A level graph is intuitively the same. When searching, it cuts out all decisions that either increase the distance from the sink or keep the distance the same. Each decision brings the search closer to the sink.
Initiate a BFS at the source node. When the BFS makes sure to not continue paths that:
Go to a previous level (increasing distance from the sink).
Go to another node at the same level (without decreasing the distance from the sink).
Now the graph is filled with only the nodes that make a difference.
Augmenting paths are actually pushing flow.
Start a DFS from the source node. Travel on edges that have capacity left to spare. Continue this until a blocking flow occurs. When one of the DFS reaches the sink, increase the capacity used by each of the nodes by the bottleneck edge capacity. If a dead end is reached, make sure to remove those edges so that the same mistakes aren’t made multiple times.
It is important to recognize that just because an edge was part of a path that did make it end doesn’t mean it can’t be re-used. 2/10 still has 8 more units left.
For example, if the path goes through edges with weights of 8/15, 3/6, and 9/10, then the flow can only be increased by 1 at each point in time.
There is nothing left to do.
A blocking flow is when there is no path from the source to the sink, which can take more water. There can still be space left on some edges, but the only paths to the source contain bottlenecks that don’t allow anymore of the space to be utilized. In this case, the algorithm will remove all the nodes that have no more potential. Such as 10/10, 5/5, and 2/2, as it is impossible to do anything more with them. If the algorithm doesn’t terminate, it will go back to step 1, making a level graph without nodes connected by full edges.
Terminating state:
When the DF occurs without changing anything, the algorithm is finished. It has found all paths, and if nothing is changed, the next iteration will have the exact same result as the last one.
Dinic’s algorithm complexity:
Time complexity on a standard graph: O(VE^2)
Time complexity of a bipartite graph: O(√VE)
Reasoning behind the bipartite time complexity:
A level graph doesn’t even need to be made. By definition, there are technically only two layers, and it’s impossible to connect to other nodes in the same layer. It will also be done in one iteration because the flow in the pipe will always be the total capacity. Each edge is a bottleneck in itself.