最小费用最大流问题的一种新算法

现有的最小费用最大流算法都有自身的缺陷，增广链的选取不当会给计算带来不便，同时费用也达不到理想的效果。鉴于对最小费用最大流算法的增广链选取和最小费用的探索，文章通过对费用差的定义给出了一种求最小费用最大流的新算法。新算法的原则是优先选择费用差最小的有向路径进行增广，当费用差相同时就选择修正后的路径。通过对最小费用最大流算法的改进，新算法易理解且便于计算。通过实例说明了新算法的有效性和执行效率。

A New Algorithm for Problem of Minimum Cost Maximum Flow

The existing algorithm for minimum cost maximum flow has its defect, improper selection of augmented chain will bring incon- venience in calculation, also the cost cannot reach the ideal effect. In view of the exploration of selecting the augmented chain and making the cost minimum,in this paper,a new algorithm for the minimum cost maximum flow is given by the definition of cost difference. The new algorithm principle is that the minimum cost difference of the directed path is preferred to augment,when the cost difference at the same time, the revised path was chosen. Through the improvement of the minimum cost maximum flow algorithm, the new algorithm is easy to understand and convenient to calculate. A practical example shows the validity and efficiency of the new algorithm.