求解网络最大流问题的标号算法

摘要：

给出了一种新的求解网络流问题的标号算法,对每个顶点进行标号,顶点有几个人弧,即有几个标号,每次在选择路径时先选取只有一个标号的路径,当所有单标号的路径走完时,再按照弧容量较大且最短的路径选择增广链.通过对Ford-Fulkerson标号算法进行改进,使得该算法容易理解,且又避免了Ford-Fulkerson标号算法在求解网络最大流问题时需经过多次的调整与标号,从而大大提高了求解最大流执行的效率.该算法通过实例给出了具体算法步骤并且表明了算法的实用性.

关键词：最大流、Ford-Fulkerson标号算法、增广链、标号

所属期刊栏目：21

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金61070234,61071167

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

页数：共3页

页码：113-115