网络最大流的新算法

摘要：

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

关键词：网络、最大流、极大一致链、消链、算法

所属期刊栏目：30

分类号：TP393.02(计算技术、计算机技术)

资助基金：国家自然科学基金项目70601036;宝鸡文理学院重点基金项目ZK0829

在线出版日期：2009-06-12（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：2357-2359