Research On Network Maximum Flow Algorithm

The network maximum flow is called special combination optimization and linear programming problem.It is in many areas there are many applications,such as freight haul in the express delivery industry,location selection of express delivery companies,information analysis of social networks,etc.In the end,it can be turned into a problem related to the maximum flow of the network.In today's era of big data background,although the network maximum flow problem has been developing for decades,the classic algorithm is difficult to copy with the computational accuracy of large-scale networks.Therefore,the study of the maximum flow problem of the network has great practical significance.In this paper,several classic algorithms for maximum flow problems are improved.The core content is as follows:1.The shortest augmented chain algorithm based on the residual network is given.The residual network is compared with the remaining network,and the structure of the residual network is found to be simpler than that of the remaining network.By weakening the constraints on the shortest augmented chain algorithm,the remaining network is replaced by the residual network,and the residual network is divided into regions,so that the operating efficiency of the algorithm is improved.By analyzing the experimental data,it can be known that the new algorithm is consistent with the maximum flow value solved by the shortest augmented chain algorithm,and the new algorithm is more efficient than the classic shortest augmented chain algorithm.2.By analyzing the capacity network graph,an improved algorithm for the shortest augmentation chain based on stratified residual network is proposed.Firstly,the arc that cannot reach the end point in the capacity network is deleted to simplify the capacity network.Secondly,the saturation arc deleted in the layered residual network is correspondingly deleted in the original network,which simplifies the process of constructing the remaining network and layering the remaining network.Thus the operating efficiency of the algorithm is improved.The experimental effects display that the improved algorithm obtains the exact solution of the maximum flow,and the running time is reduced compared with the shortest augmented chain algorithm.3.The deficiencies of the Ford-Fulkerson algorithm are pointed out.Based on the breadth-priority search and the augmented chain repair method,a maximum-flow solution algorithm is given.Simulation of the new algorithm on MATLAB software,the simulation effects display that the new algorithm is more efficient than the Ford-Fulkerson algorithm.