Maximum Flow Algorithm And Applied Research

The maximum network flow problem is an important part of network flow theory, theminimum cost maximum flow problem is the extension of maximum flow problem. All of themare widely used in many fields and have a wide range of applications, many practical problemscan be transformed into the maximum flow problem. For the maximum flow problem, thealgorithm is the Ford-Fulkerson algorithm and the maximum flow algorithm. The paper firstlyintroduces some basic definition、basic theorems and two classic algorithms of maximum flowalgorithm and minimum cost maximum flow theorems, all of them have the problem of largeamount of calculation, complicate steps, and improper method to choose augmenting chains. Thepaper does the following work:Firstly, the improved algorithm is given for solving the maximum flow problem ofmaximum network, it’s the capacity difference algorithm. The algorithm is achieved by selectingappropriate augmented chain to calculate the maximum flow. The selecting principles ofextended chains are the shortest path, minimum capacity difference, maximum residual capacityand maximum capacity. The process of algorithm can be completed in a chart and reduces thecomplexity of the algorithm.Secondly, the paper presents a new algorithm for the minimum cost maximum flowproblem, which is called the cost difference algorithm. The core of algorithm is selection ofaugmented chains, the principle of first algorithm is:chose the path of minimum cost difference,if there are multiple paths of same cost difference, chose the minimum cost and, chose theshortest one when there are some paths have the same cost and. The algorithm optimize theproblems if improper selection augmenting chains of classical algorithms, the calculation isconvenient and easy to implement.Thirdly, the capacity and cost difference algorithm is formed on the base of the two newalgorithms. It considers the cost and flow of network, which has certain application significance.Finally, the other practical and theoretical application of maximum flow algorithm are given,and introduce the related knowledge of Lingo software also introduced, and Lingo language isused to design three new algorithms for their feasibility of using and correctness.