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

An Improved Algorithm for Solving Problem of Network Maximum Flow

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

The maximum network flow problem is one of the classical problems in graph theory,there are many classical algorithms for them,but all theories have shortcomings. For the shortcomings,the algorithm is improved by introducing the concept of differential capac-ity. The principle of improved algorithm is that the shortest path and maximum differential capacity is priority selection. When the length of path and differential capacity are the same,can choose the revised path,so that each augmentation can make an arc reach saturation at least. An practical example is given to demonstrate the feasibility,all of the procedure can be completed in one diagram,the intuition is strong and easy to calculate,the new algorithm is more effective than the traditional algorithm.