有向网络中无环最小饱和流问题及其算法

• 作者: 吴薇薇 宁宣熙
• 来源期刊: 南京航空航天大学学报
• 学科: 数学
• 关键词: 无环最小饱和流 堵塞截面 有条件最长增广路 最小完全截集
• 年，卷（期）: 2007,（5）
• 页码范围: 685-690
• 页数: 6页
• 分类号: O157.5
• 字数: 5530字
• 语种: 中文
• DOI: 10.3969/j.issn.1005-2615.2007.05.027

摘要

假设网络的初始流为零流,以最大堵塞截面为准堵塞截面,找出从源点到汇点的包含准堵塞截面弧最多的有条件最长增广路对网络进行增流,直至网络达到饱和,并对该算法进行了复杂性分析.利用该算法对多个网络进行论证,结果表明利用有条件最长增广路算法计算出的最小饱和流值与仿真计算以及与双向增流算法计算得到的结果基本相同,增流次数大大减少,且求解的结果避免了在封闭环路中的流量流动,进一步优化了最小饱和流值.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	宁宣熙	南京航空航天大学经济与管理学院	204	2932	27.0	42.0
2	吴薇薇	南京航空航天大学民航学院	40	237	9.0	13.0