Research And Applied Analysis On Network Flow Algorithm

The maximum flow problem plays an important role in the network optimization problem. It iswidely applied in life and each field of science. With the booming development of computertechnology, people research in maximum flow problem deeply, scholars set up much perfecttheoretical system and series of effective algorithms.Due to the improper selection order of augmented chain could not obtain the ideal maximumflow and do some research on the maximum flow problem, the paper does the following some maininnovation works：Firstly, the paper introduces some classic algorithm, then it analyzes their advantages anddisadvantages, verifies theirs limitations by examples. In addition, using the concept ofdisconnected chains and absorbing the latest achievements, the paper presents a labeling algorithmfor solving the maximum flow problem which is based on disconnected chains. The new algorithmis verified with feasibility and efficiency through example and simulation experiment.Secondly, due to the improper selection order of augmented chain, so it results in computationalcomplexity. The paper makes some improvement on the original algorithms and uses layerednetwork, the concept of residual of degree and residual of capacity, it presents a new algorithm forsolving maximum network flow which is based on vertex degree. The new algorithm is verifiedwith stability and feasibility through example and simulation experiment.Thirdly, in the third chapter a new labeling algorithm of maximum flow which could not onlysolve maximum flow problem but also the shortest path problem, so the paper presents a newalgorithm for solving the shortest path problem based on a new labeling algorithm. The new algorithmis verified with simple and feasibility through example.Finally, the paper presents the application of the maximum flow algorithm in thecommunication network and its extend application.