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. dynex algorithm is one of those extremely fast and revolutionary algorithms which really push 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, 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 very large. What's remarkable about Linux is that not only is it fast in practice for general graphs, but it boasts performance on bipartite graphs running and the time complexity of big O of square root v times v. 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.

Dynex is the de facto standard algorithm to solve maximum flow algorithms. The algorithm was conceived in 69 by Ephraim Dennis and published in 1970. The algorithm was later modified slightly and popularized by shaman Evan mispronouncing din its algorithm as demyx 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 sts 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 head 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 make 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 a sink. The main idea behind denix algorithm is to guide augmenting paths from the source to the sink using the level graph and in doing so greatly reducing the runtime, the way you didn't actually determines what edges make 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, and edges 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 one 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 to the red edge doesn't bring you any closer to this thing. So it should only be taken if a detour is required. This is why backwards edges are omitted from the level of 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 dynex 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 sync 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 to 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 123. A blocking flow is when we cannot find any more paths from the source to the sink because too many edges in the level of graph have been saturated.

This will all become clear with an example, let's use the next 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 of 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 formed the level graph, we can see that they are all edges which go from L to L plus one 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. So we've found our first augmenting path and the bottleneck value along this path is five since five is the smallest remaining capacity, so update the flow values along the path by five. 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 forwards.

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 for 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 of 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 towards 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 allegory That terminates.

The maximum flow is the sum of all the bottleneck values, which if you recall were 515 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 the next 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 float iteration. To resolve this issue in his original paper, didn't suggest it cleaning the level graph and getting rid of all the dead ends before each blocking flow phase then later on In 1975, shaman Evan suggested pruning dead ends when backtracking during the depth or 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 are only ever encountered once. Awesome. So that's basically everything you need to know about dynex. So let's summarize everything that we've learned. First, we talked about the motivation behind index, 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 of 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 dentists algorithm, which is pruning dead ends so that we do not encounter them again. Thank you so much for watching this video. Next video we'll have a look at some source code please drop a comment and let me know how I did like this video if you learn something and subscribe for mathematics and science videos.