基于最短增广链的最大流改进算法
2017-09-01赵礼峰纪亚劲
计算机技术与发展 2017年8期
关键词:效率
赵礼峰,纪亚劲
(南京邮电大学 理学院,江苏 南京 210023)
基于最短增广链的最大流改进算法
赵礼峰,纪亚劲
(南京邮电大学 理学院,江苏 南京 210023)
网络最大流是经典的组合优化问题,它的经典算法主要有三种,分别是Ford-Fulkerson算法、最短增广链算法(Dinic算法)和预流推进算法。Ford-Fulkerson算法中由于增广链的选取任意性而有时无法得到理想的最大流。最短增广链算法在分层剩余网络中寻找最短增广链,从而避免了增广链选取的任意性。但最短增广链算法在求解最大流过程中每次增广都需要重新寻找最短增广链,利用率不高。针对这一问题,提出了一种修复最短增广链的新算法。该算法在沿最短增广链调整流量之后,删除最短增广链流量为零的弧,且寻找合适的路径修复最短增广链,从而提高了最短增广链的使用效率,减少了最短增广链的搜索次数。应用新算法进行了BA无标度网络建模仿真。实验结果表明,该算法运行效率要高于最短增广链算法。
最大流;分层剩余网络;最短增广链;BA无标度网络
0 引 言
网络最大流问题是图论中极其重要的分支,是经典的组合优化问题,也可以看成特殊的线性规划问题[1]。它在运筹学、计算机、工程等众多科学领域中有着广泛的应用[2-3],例如,运输问题、分派问题、通信问题等都可以转化为网络最大流模型来解决。因此,研究网络最大流算法具有很重要的意义。
至今为止,网络最大流问题的研究已经有50多年的历史,现已建立了较为完善的理论并且提出了一系列经典算法。……
登录APP查看全文
