This paper presents a new strongly polynomial time algorithm for the minimum cost flow problem, based on a refinement of the Edmonds-Karp scaling technique. The present algorithm solves the uncapacitated minimum cost flow problem as a sequence of O(nlogn) shortest path problems on networks with n nodes and m arcs and runs in O(nlogn(m+nlogn)) time. Using a standard transformation, this approach yields an O(mlogn(m+nlogn)) algorithm for the capacitated minimum cost flow problem. This algorithm improves the best previous strongly polynomial time algorithm, due to Z. Galil and E. Tardos, by a factor of n2/m. The present algorithm for the capacitated minimum cost flow problem is even more efficient if the number of arcs with finite upper bounds, say m', is much less than m. In this case, the running time of the algorithm is O((m'+n)logn(m+nlogn)).
