The cycle-canceling algorithm is one of the earliest algorithms to solve the minimum-cost flow problem. This algorithm maintains a feasible solution x in the network G and proceeds by augmenting flows along negative-cost directed cycles in the residual network G(x) and thereby canceling them. For the minimum-cost flow problem with integral data, the generic version of the cycle-canceling algorithm runs in pseudopolynomial time, but several polynomial-time specific implementations can be obtained by specifying the choices of cycles to be canceled. In this paper, we describe a new polynomial-time implementation of the cycle-canceling algorithm. Our algorithm is a scaling algorithm and proceeds by augmenting flows along negative cycles with sufficiently large residual capacity. Further, it identifies such a cycle by solving a shortest path problem with nonnegative arc lengths. For a network with n nodes and m arcs, our cycle-canceling algorithm performs O(m log(nU)) augmentations and runs in O(m(m + n log n) log (nU)) time, where U is an upper bound on the node supplies/demands and finite arc capacities. We also show that the cycle-canceling algorithm (i) can solve the uncapacitated minimum-cost flow problem in O(n(m + n log n) log (nU)) time; (ii) can obtain an integer optimal solution of the convex cost-flow problem in O(m(m + n log n) log (nU)) time; and (iii) can be modified so that it runs in O(m(m + n log n) min {log (nU), m log n}) time, which is a strongly polynomial time bound.
