Research On Improved Algorithm Of Maximum Flow In Network

The maximum flow problem of the network is a classic combinatorial optimization problem.It is a problem of rational distribution of traffic from the source point to the sink point in the network.For the direct flow of the maximum flow in the real life network,the maximum flow algorithm is used in many fields.Tools to use,such as the traffic flow problem of the road network,the distribution of water flow among cities,etc.These are all converted into the problem of solving the maximum flow value for thinking.At present,many researchers have also proposed various algorithms for solving the maximum flow problem of the network,and have also obtained more outstanding scientific research results in their fields.However,with the rapid development of science and technology and network scale,the phenomenon of network congestion has also prevailed.Classical algorithms are difficult to deal with complex large-scale networks.Therefore,further improvement of classic algorithms has practical value for studying the maximum flow of the network.This paper proposes improvements based on the classic network maximum flow algorithm,the main results are as follows:1.An algorithm for solving the maximum flow of the network based on the arc capacity ratio is given.Due to the arbitrariness of the shortest augmentation chain algorithm to choose augmentation chain,it is proposed to use arc capacity ratio to preferentially select the shortest augmentation chain containing key arcs for augmentation.The experimental results prove that the new algorithm can avoid the waste of some arc capacity,increase the maximum flow value of the network,make the maximum flow value obtained by it more accurate,and have shorter running time and higher efficiency;2.By analyzing the blocking amount of each node in the area of ??the capacity network graph,an algorithm for solving the maximum flow of the network based on the blocking amount of the intermediate node is proposed.The capacity network nodes are first divided into regions,and the blocking amount of the nodes in the area is used to selectively increase The wide path is augmented,and finally the flow value of the maximum flow of the network is solved.In the experimental simulation,the proposed new algorithm is more efficient than the Dinic algorithm in the BA scale-free random network;3.The shortest augmentation chain algorithm based on improved hierarchical residual network is proposed.Point out the defects of the original layered residual network in the algorithm,delete meaningless arcs on the basis of it,reduce the complexity of the layered residual network,and select the shortest path that can be expanded according to certain rules to avoid the augmented path The arbitrariness of choice.Experimental results show that the new algorithm is more efficient than the traditional shortest path algorithm.