An O(nm2) time algorithm for solving minimal cost network flow problems

The minimal cost network flow problem with arbitrary lower and upper bounds on arcs flow and non-zero node numbers is considered in this paper. In a two stage procedure this problem is transformed to an equivalent circulation problem with zero lower bounds on arcs flows. A new algorithm based on the complementary slackness conditions for solving the circulation problem is proposed. The algorithm starts with trivial zero flow and node potentials and then using a back and forth search process, tries to optimize all arcs flows. The run time of the algorithm is O(m²n).