计算机应用 ›› 2014, Vol. 34 ›› Issue (4): 969-972.DOI: 10.11772/j.issn.1001-9081.2014.04.0969

• 网络与通信 • 上一篇    下一篇

最大动态流关键弧的改进算法

刘杨杨,谢政,陈挚   

  1. 国防科学技术大学 理学院,长沙 410073
  • 收稿日期:2013-10-21 修回日期:2013-12-26 发布日期:2014-04-29 出版日期:2014-04-01
  • 通讯作者: 刘杨杨
  • 作者简介:刘杨杨(1990-),男,湖北襄阳人,硕士研究生,主要研究方向:网络最优化;
    谢政(1960-),男,湖南衡阳人,教授,主要研究方向:网络最优化;
    陈挚(1965-),男,湖南湘乡人,副教授,主要研究方向:网络最优化。

Improved algorithm for vital arc of maximum dynamic flow

LIU Yangyang,XIE Zheng,CHEN Zhi   

  1. College of Science, National University of Defense Technology, Changsha Hunan 410073, China
  • Received:2013-10-21 Revised:2013-12-26 Online:2014-04-29 Published:2014-04-01
  • Contact: LIU Yangyang

PDF

摘要：

针对时间容量网络的最大动态流的关键弧问题，首先分析了经典的Ford-Fulkerson最大动态流算法，在此基础上简化了最大动态流算法，并由此提出一个基于最小费用增广路来寻找最大动态流关键弧的改进算法。算法将计算新网络最大动态流时共有的最小费用路保留，去掉了自然算法中重复的计算。的效率更高。

Abstract:

For the vital arc problem of maximum dynamic flow in time-capacitated network, the classic Ford-Fulkerson maximum dynamic flow algorithm was analyzed and simplified. Thus an improved algorithm based on minimum cost augmenting path to find the vital arc of the maximum dynamic flow was proposed. The shared minimum augmenting paths were retained when computing maximum dynamic flow in new network and the unnecessary computation was removed in the algorithm. Finally, the improved algorithm was compared with the original algorithm and natural algorithm. The numerical analysis shows that the improved algorithm is more efficient than the natural algorithm

中图分类号: 

版权所有 © 2021 四川计算机应用杂志社有限公司
蜀ICP备 05010208 号-3　新出网证(川)字026号
技术支持：北京玛格泰克科技发展有限公司
访问总数：
今日访问：