J4 ›› 2011, Vol. 46 ›› Issue (6): 99-102.

• Articles • Previous Articles     Next Articles

A new algorithm for solving minimum cost flow with the duality principle

XIONG Deguo1, HU Yongwen1, SHI Jianming2   

  1. 1.  School of Energy Science and Engineering, Henan Polytechnic University, Jiaozuo   454000, Henan, China;
    2. College of Information and Electronic Engineering, Muroran Institute of Technology,  Muroran, 0500071,   Hokkaido,  Japan
  • Received:2010-10-17 Online:2011-06-16 Published:2011-12-19


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

No related articles found!
Full text



No Suggested Reading articles found!