Several Research And Analysis On Network Algorithm

Network flow issue, as a part of operatinal research, mainly studies network optimizationproblems. It plays an important role in engineering and science. Its primary coverage includesshortest path, maximum flow and minimum cost flow problems, With the development ofinformation technology, researchers have established a more complete theory, proposed a set ofrelevantalgorithms,andachievedremarkableresults.This study focuses on oil transportation network model, analyzes,compares and improvesmaximumflow,minimumcostflowalgorithmandrelatedissues.Firstly, in order to solve maximum flow in networks, this thesis introduces three mainalgorithms: the FordFulkerson marking method, the shortest path algorithm and the augmentedpreflow push algorithm. Through specific examples, the author has demonstrated the limitationsof the algorithm. Based on the analysis of the above algorithms'characteristics and through thelatest research results of the absorption maximum flow algorithm, this thesis proposes two newalgorithms for Maximum flow which can be testified by examples. Secondly, the authorintroduces the Minimum Cost Flow including negative circuit algorithm, minimum cost pathalgorithm, and the maximum flow with a given budget algorithm and the minimum costmaximum flow algorithm. Before the introduction of the minimum cost flow algorithm, thisthesisgivesaneasymethodsolvingtheshortestpathbetweentwopointsinsmall-scalenetworks.Finally,thethesisproposesthebestsolutionsforoiltransportationnetwork.All of the given algorithms are followed with relevant examples although examples can notbe used as a standard to judge one algorithm. From the standpoint of comparison, the use ofcertainrepresentativeexamplescouldbeaconsideredmethod.