网络最大流问题的改进算法

摘要：

网络最大流问题是图论中的经典问题之一，对于最大流问题有很多经典的算法，但这些经典算法皆有不足之处。针对其不足，文中通过引入容量差的概念，对算法进行了一些改进。改进算法的原则是优先选择路径最短且容量差最大的路径进行增广，若当路径长度一样并且容量差也一样时就要对其修正，然后选择修正后的路径，这样每次增广至少使一条弧达到饱和。通过实例说明了改进算法的可行性，整个运算过程可以在一个图上完成，直观性强并且方便计算，较传统算法更为有效。

关键词：最大流、容量差、增广链、最短路径

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

资助基金：国家自然科学基金资助项目GZ210039

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

页数：共3页

页码：54-56