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

摘要：

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

关键词：最小费用最大流、费用差、费用和、增广

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目GZ210039

在线出版日期：2014-01-22（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：130-132