Vertex-based Algorithm For Solving Maximum Flow Of Network

The network maximum flow problem is a combination of optimization problems in operations research and graph theory,which involves a very large range.Many examples in daily life and production can be abstracted into mathematical models of the network maximum flow problem to be solved.For example,traffic flow in transportation network,oil flow in pipeline network,data flow in information network,etc.So far,the issue of maximum flow has been in development for more than 60 years,and many experts and scholars have contributed a lot of research results.However,according to the vigorous growth of various networks,there is a need for a faster and better solution to the maximum flow problem of the network to face the actual needs of these networks.Therefore,it is of certain value to explore the network maximum flow problem in a deeper level.In this paper,based on the classic algorithm of the maximum flow problem in the network,some improved algorithms are proposed,as follows:1.An improved algorithm of maximum flow based on cross vertices is proposed.For the network graph with cross vertices,after constructing its layered residual network,when searching for an augmentation chain,the vertices associated with the source point and having the smallest tolerance are searched first as the next step of the augmentation chain Advance point.After determining an augmentation chain,then consider augmenting with the previous augmentation chain with duplicate vertices.The new algorithm and the shortest augmented-chain algorithm are simulated in MATLAB,and finally the performance of the new algorithm is better than the shortest augmented-chain algorithm.2.A network maximum flow algorithm based on resetting vertex index is proposed,which follows the idea of vertex layering in the classic algorithm,and vertex is selected according to four factors: number of layers,source arc capacity,sink arc capacity and vertex tolerance In order.Then select the augmentation chain according to the corresponding rule.This rule can ensure that the shortest augmentation chain is selected first,and can quickly find all augmentation chains in an orderly manner.It is verified by example that the performance of the algorithm is better than the Ford-Fulkerson algorithm.3.The shortest augmentation chain algorithm based on the degree difference is proposed.The algorithm is based on the shortest augmentation chain algorithm to perform augmentation along multiple augmentation paths at the same time.It does not take into account that the augmentation order will affect the maximum flow value.Three amendment principles were proposed.It is verified by example that the performance of the new algorithm is better than the shortest augmented chain algorithm.