The Research Of The Maximum Flow And The Minimum Cost Algorithm

In real life, there are many problems about flow. On the basis of perfect theory, with the fast development of computer technology and internet technology, the maximum flow is widely used in communication,physics,electric power and the other science. As the basement of modern communication, network-flow mainly includes the minimum flow,the minimum cost and the maximum flow,the maximum flow and so on.This paper mainly studies the use of real transportation network in the minimum cost,the minimum cost and the maximum flow and the maximum flow. It also discusses the analysis and improvement of algorithms.In the first part, this paper mainly states the development of maximum flow and the minimum cost. It also studies the current situation and the meaning of research background at home and abroad.In the second part, at first, this paper introduces the basic concept and relevant theory about the maximum flow and the minimum cost. It states the solving method and complication of Ford-Fulkerson labeling algorithm,the shortest augmented chain algorithm and the augmented preflow push algorithm and realize the above the algorithms with examples in detail.In the end, it simply introduces the method to resolve the minimum cost, including the way to solve the minimum cost, such as negative loop algorithm,the minimum cost algorithm,the minimum cost and the maximum flow algorithm and fixed budget the maximum flow algorithm.In the third part, on the basis of current the maximum flow algorithm, this paper puts forward a new labeling algorithm to solve the maximum flow and proof it through examples.In the fourth part, on the basis of the minimum cost algorithm, this paper puts forward a algorithm to solve the minimum cost and comes up with the best transportation program in the system of natural gas transportation.