求解最小费用最大流的新方法

• 作者: 宋常城 白睿 赵礼峰
• 来源期刊: 计算机技术与发展
• 学科: 工学
• 关键词: 最小费用最大流 最大容量 单位费用 剩余网络
• 年，卷（期）: 2012,（5）
• 所属期刊栏目: 智能、算法、系统工程
• 页码范围: 94-96
• 分类号: TP301.6
• 字数: 2962字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-629X.2012.05.024

摘要

文中给出了一种求解网络最小费用最大流的新方法,寻找由始点到终点的每条有向链,找到有向链可通过的最大容量,根据最大容量计算出此条有向链的最小费用最大流,根据最大容量和最小费用最大流可以计算出单位费用.选取单位费用最小的有向链进行最大容量的增广.文中通过对最小费用路算法进行改进,使得该算法容易理解,却又避免了最小费用路算法每次都要经过剩余网络进行增广,从而大大提高了求解最小费用最大流执行的效率.该算法通过实例给出了具体算法步骤并且表明了算法的实用性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	赵礼峰	南京邮电大学理学院	47	251	9.0	12.0
2	宋常城	南京邮电大学理学院	4	58	4.0	4.0
3	白睿	南京邮电大学理学院	4	58	4.0	4.0