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