最大流问题的最短增广链改进算法

• 作者: 赵礼峰 邵丽萍
• 来源期刊: 计算机技术与发展
• 学科: 工学
• 关键词: 最大流 最短增广链 剩余网络 分层剩余网络 BA无标度网络
• 年，卷（期）: 2019,（5）
• 所属期刊栏目: 智能、算法、系统工程
• 页码范围: 58-61
• 页数: 4页
• 分类号: TP301.6
• 字数: 3644字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-629X.2019.05.012

摘要

BA无标度网络是现实中常见的网络,在该网络中,任意两节点之间有极大可能存在多条路径,若用Ford-Fulkerson算法寻找增广链,效率不高且步骤繁杂.同时,在当今大数据时代背景下,随着网络规模的增加,提高算法效率成为解决大规模网络最大流问题的关键.为了改善以上不足,文中在最短增广链算法的基础上作了一些改进,提出了最短增广链改进算法.该算法基于最短增广链算法,删除原网络中没有起作用的弧;在分层剩余网络中删除的饱和弧,相应的在原网络中删除该弧,降低构建剩余网络和分层剩余网络的复杂性,从而优化最短增广链算法.实验结果表明,在BA无标度网络中该算法与最短增广链算法的计算结果相同,并且运行效率比最短增广链算法有所提高.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	赵礼峰	南京邮电大学理学院	47	251	9.0	12.0
2	邵丽萍	南京邮电大学理学院	3	2	1.0	1.0