In this paper, we present a new polynomial time algorithm for solving the minimum cost network flow problem. This algorithm is based on Edmonds-Karp's capacity scaling and Orlin's excess scaling algorithms. Un...
详细信息
In this paper, we present a new polynomial time algorithm for solving the minimum cost network flow problem. This algorithm is based on Edmonds-Karp's capacity scaling and Orlin's excess scaling algorithms. Unlike these algorithms, our algorithm works directly with the given data and original network, and dynamically adjusts the scaling factor between scaling phases, so that it performs at least one flow augmentation in each phase. Our algorithm has a complexity of O(m(m + n log n) log(B/(m + n))), where n is the number of nodes, m is the number of arcs, and B is the sum of the finite are capacities and supplies in the network. (C) 1999 Elsevier Science B.V. All rights reserved.
暂无评论