一种求解网络图最大流的新算法

A New Algorithm for Solving Maximum Flow

给出一种求解网络最大流的新算法,该算法是针对增广链选取的顺序不当而无法得到理想的最大流,且在计算过程中每步都需要画一个网络图等问题进行的改进。利用分层及度差的概念,在选择增广链时优先选择路径最短且度差较大的路径,相同层次度差相同时优先选择容差较大的路径,在饱和的弧上画上终止符。最后用实例进行了验证并和Ford-Fulkerson算法做了比较,体现了它的高效性,避免了标号,且只需要在一个图上即可完成。整个运算过程直观性强,计算方便。

It provided a new algorithm for solving maximum network flow. Due to the improper selection order of augmented chain could not obtain the ideal maximum flow and each step in the process of calculation needs to draw a network diagram, the algorithm does some improvement. The new algorithm makes use of layered network and the concept of degree of difference, gives priority to the shortest path and greater degree of difference when choosing augmenting path. It gives priority to the greater allowance path when degrees of difference are same under the same layer. And draws terminators on the arcs have reached saturation. Finally the algorithm is proved through the example and makes comparison with Ford-Fulkerson algorithm, showing its efficiency, and avoiding the labeling process, the entire process only needs drawing a diagram to be completed. It is strongly intuitive and convenient to calculate.