A Permissible Edge Algorithm For Solving Minimum Cost Flow By A Dual Approach

This paper is mainly concerned with the minimum cost flow problem, and some main algorithms have been studied systematically. A new algorithm named permissible edge algorithm is proposed to solve the minimum cost flow which holds the complementarity conditions to the dual problem and finds a desired flow or minimum cost flow by modifying the potential to obtain permissible edge and labeling for each node on all permissible edges to search augmenting path to increase the value of the flow. Unlike the existing algorithms, it needs not to construct a residual network nor find a shortest path to the new algorithm. The validity of the new algorithm is proved and its complexity is also given. According to the results of the numerical experiment on random network, the new algorithm has a good behavior on dense network.The shortest path problem,as a special case of minimum cost flow problem,is used widely in theory and practice. Besides, most of the existing algorithms for solving minimum cost flow need to search shortest path in residual network. In view of this, the shortest path problem has also been given sufficient attention. And a matrix method is aslo proposed to solve the shortest path problem according to Dijkstra's algorithm, which can easily get the distance and the path from the source node to other nodes in weight network with simple calculation and label in the last obtained matrix.