求解最小费用流的一种新算法

• 作者: 刘艳清 纪亚劲 赵礼峰
• 来源期刊: 计算机技术与发展
• 学科: 工学
• 关键词: 最小费用流 Dijkstra算法 余网络 ER随机网络
• 年，卷（期）: 2018,（1）
• 所属期刊栏目: 智能、算法、系统工程
• 页码范围: 108-111,115
• 页数: 5页
• 分类号: TP301.6
• 字数: 3505字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-629X.2018.01.023

摘要

网络最小费用流问题是经典的双目标优化问题,其中利用的图论方法主要有负费用回路算法和最小费用路算法.最小费用路(Busacker-Gowan)算法每次增广流值之前都需要搜索一次最小费用路径,导致算法复杂度偏高,并且该算法是在剩余网络的基础上进行增广,使得该算法在计算预定流值最小费用流时有点冗余.针对这些不足,提出了一种求最小费用流的新算法.该算法首先利用改进的Dijkstra算法一次搜索出所有的源点至汇点费用路径,并且在余网络中增广流值.由于余网络比剩余网络构造简单,所以最终提高了算法的时间效率.仿真实验表明,在ER随机网络中提出算法和经典算法的计算结果相同,并且提出算法不管是在稀疏网络还是非稀疏网络中其运行时间比经典算法都要少,同时更适用于稀疏网络.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	赵礼峰	南京邮电大学理学院	47	251	9.0	12.0
2	刘艳清	南京邮电大学理学院	2	5	2.0	2.0
3	纪亚劲	南京邮电大学理学院	2	8	2.0	2.0