网络最大流的新算法

• 作者: 孙小军 王志强
• 来源期刊: 计算机工程与设计
• 学科: 工学
• 关键词: 网络 最大流 极大一致链 消链 算法
• 年，卷（期）: 2009,（10）
• 所属期刊栏目: 网络与通信技术
• 页码范围: 2357-2359
• 页数: 3页
• 分类号: TP393.02
• 字数: 2120字
• 语种: 中文

摘要

针对Ford-Fulkerson标号算法在求解网络最大流问题时需要经过多次的标号与调整,从而导致算法效率随着网络规模的增大和网络复杂性的增加而降低的不足,受现实生活中水流流动的启发,通过引入极大一致链的概念提出了一种求解网络最大流问题的消链算法.该算法通过寻找容量网络中的极大一致链,并根据所得到的极大一致链对网络逐步地进行调整,避免了标号算法的标号过程,同时由于极大一致链的极大性加速了链的消去过程.算法分析和算例表明了该算法的有效性和实用性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	孙小军	宝鸡文理学院数学系	57	242	9.0	11.0