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

• 作者: 刘杨杨 谢政 陈挚
• 来源期刊: 计算机应用
• 学科: 工学
• 关键词: 最大动态流 时间重复流 关键弧 最小费用增广路 最小动态截
• 年，卷（期）: 2014,（4）
• 所属期刊栏目: 网络与通信
• 页码范围: 969-972
• 页数: 4页
• 分类号: TP301.6
• 字数: 5257字
• 语种: 中文
• DOI: 10.11772/j.issn.1001-9081.2014.04.0969

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈挚	国防科学技术大学理学院	11	35	3.0	5.0
2	谢政	国防科学技术大学理学院	15	51	4.0	6.0
3	刘杨杨	国防科学技术大学理学院	2	4	1.0	2.0