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

• 作者: 赵礼峰 陶晓莉
• 来源期刊: 计算机技术与发展
• 学科: 工学
• 关键词: 最小费用最大流 费用差 费用和 增广
• 年，卷（期）: 2014,（1）
• 所属期刊栏目: 智能、算法、系统工程
• 页码范围: 130-132
• 页数: 3页
• 分类号: TP301.6
• 字数: 2248字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-629X.2014.01.033

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	赵礼峰	南京邮电大学理学院	47	251	9.0	12.0
2	陶晓莉	南京邮电大学理学院	2	13	1.0	2.0