Abstract:

A new algorithm is proposed to solve the problem of minimum cost flow by a dual approach, which held complementarity conditions to the dual problem and found a desired flow by modifying the potential and labeling for each node of the network. Unlike existing algorithms, the new algorithm did not construct a residual network nor find the shortest path. The validity of the new algorithm is proved, and an example is given to illustrate the behavior of the proposed algorithm.

Key words:  minimum cost flow; duality principal; new algorithm