This is the 15th day of my participation in the August More text Challenge. For details, see: August More Text Challenge
Maximum Flow Problem belongs to the category of graph theory. In the Maximum Flow Problem, the graph we study is a directed weighted graph, that is, all edges have directions and weights. There are many nodes in this diagram.
- The starting node is denoted by S (source).
- The endpoint is represented by t (target)
To visualize the maximum flow problem, we want to transport water from the starting point S to the end point T. To explain the maximum flow problem, all the edges (pipes) connected by the intermediate nodes have a certain carrying capacity. Here is the concept of capacity. The capacity or the carrying capacity of the pipeline can be thought of as the amount of water that can pass through the pipeline per second, the fewer cubic meters of water that can be transported from the beginning to the end. This is the maximum flow problem. So for the maximum flow problem, what information do we need and what does it all mean?
First of all, we need to have a directed graph consisting of nodes and the edges between nodes, and then we need to support the starting point and the end point of the maximum flow in the graph, and what we need to do is to find some reasonable path to maximize the flow per unit time from the starting point to the end point. That is, the maximum amount of water that can be transported from start to finish under the current network.
As shown in the figure above, the weight of the edge can be understood as the capacity of the water pipe. Here, the weight of the edge connecting V1 and V3 is 2, which means the carrying capacity of the water pipe is 2. Before we start, we need to introduce the concept of residual, that is, the capacity of the pipe minus the actual flow. That is, how much of the carrying capacity of the pipe is still unused. At the beginning, when there is no traffic passing through the network, when there is no traffic in the diagram, the idle amount is equal to the carrying capacity of the pipe. The following two graphs are listed for your observation. The left is the original picture, and the right is the idle amount of the pipe.
As shown in the figure below, the next series of operations are performed on the residual graph. First we try to find a simple path from the beginning to the end, the so-called simple path is that there is no loop in the path. There are many ways to find a simple path, in which we first treat the graph as a powerless graph, and then find the shortest path as the simple path of the graph. Next we find a path, and then standard the path with color lines as shown below (left). This path goes from the starting point s to v2, v4 and then it flows to the end point. The upper weights of the path are 2, 2, and 3 respectively, and the minimum weight is 2. Due to the short board effect, all the paths can only pass through 2 portions of water at most, and we 2 portions of water pass through this path, so the idle amount on the path will be subtracted by 2 respectively and become 0, 0 and 1, as shown in the figure on the right. Now we have an update to the idle volume graph.
I observed that the two edges between S and v2 and v2 and V4 have zero free amount, which means they already contain no water flowing through these two pipes, so we can remove these two edges from the free graph shown on the left. That completes the first cycle. So what I’m going to do is I’m going to repeat this, and I’m going to find another simple path in the free graph, s, v1, V3, t, and since the minimum weight on this path is two I’m going to subtract two from all the free things, and I’m going to find that the free things from V1 to v3 are zero when I subtract two, so I’m going to remove the edge between them, So the second iteration of the idle graph turns it into the bottom right.
Let’s move on to the next loop, and I won’t explain it this time, but I think you can see how you got these pictures, and if you’re still not sure how you got these pictures you can leave me a comment.
Now when we look at the bottom right after the last cycle, we can no longer find any path for the water to flow from the beginning to the end. When the start-to-end path cannot be found in the idle graph, we can exit the loop.
Now we have a loop and get the residual graph. We can calculate the Flow in the network by using Flow = Capacity – residual
Using this formula, we can calculate the figure on the lower left, where 2/2 represents flow/capacity, that is, the flow of 2 pipes through 2, and the idle amount is 0.
It is not difficult to see from the figure on the left that the total traffic of the network is 5, so how to calculate the network traffic of 5? The outgoing traffic from the starting point 3 is 2 + 3, so the maximum traffic of the network is 5.
But let’s look at the problem with this algorithm, and the problem with this algorithm is that there is no guarantee that the solution is the maximum flow, and let’s illustrate this problem with an example. Let’s go back to the example above. The algorithm can find the maximum flow depending on the order of the search path. If you find the path s, v1, V4, t in a loop, you get the updated idle amount graph using the algorithm described already, as shown in the lower right.
And then I’m going to go ahead and get the free graph and find another path s, v1, V3, T and then I’m going to update the free graph and I’m going to get to the bottom right, and then I’m going to look at it and I’m going to get the free graph, and I’m going to send this free graph, and I’m not going to be able to find the path from the start to the end, and I’m going to get to the free graph that I got.
Ok, so we’re taking the capacity of the original graph and we’re subtracting the amount of free in the idle graph and we get the bottom left graph and so, by calculating the amount of flow out from the starting point we find that the maximum flow from the top graph is 4 which is less than the last one was 5 so this is clearly not the maximum flow from this graph.
From the above example we explain that with this simple method it is possible to find a network flow that is not the maximum network flow because of the order in which the path is chosen. This is not the highest flow. In fact, there is a blocking flow in the above diagram. Why is it called a blocking flow? Of course, the maximum flow is also a blocking flow. Obviously, when the maximum flow occurs, the network cannot pass more traffic.
- The algorithm inputs a directed graph in which the starting point s and the ending point T are indicated
- The goal is to find some way to get as much water as possible from the beginning to the end
- Constraints: Each edge has a weight, which represents the capacity of the water pipe. Therefore, the water pipe flow cannot exceed the capacity
algorithm
- Build the residual graph, which is the original at the beginning
- Then I go through the loop, find a simple path, find the edge with the least weight of the path, which is the path bottleneck, subtract the bottleneck from the weight of all the edges on the path, and then update the free graph, and look at the edge in the free graph that has zero free amount, and remove it from the free graph.
