基于预流推进的最小标号最大流算法

Lowest label algorithm for minimum cut / maximum flow based on preflow push

针对原始最高标号预流推进算法中的回溯现象导致其在部分网络中执行效率低下的问题,提出了基于预流推进的最小标号算法。该算法仍以预流推进为基础,但在选取活跃节点时依据贪心原则寻找最小标号活跃节点作为调整点,同时还需构造回溯检验方法终止回溯现象以提升算法效率。在仿真实验中,该算法能够适应各类复杂网络,并在稀疏网络中具有最高标号预流推进算法5倍以上执行速度;在被应用于图像分割领域时,该算法也具有50%以上性能提升。提出的基于预流推进的最小标号最大流算法能够满足大规模网络流量分配、计算机视觉图像处理等需求。

Aiming at the problem of the low execution efficiency in the part of the network caused by the backtracking phenomena of the original highest label preflow push algorithm, the lowest label algorithm based on preflow push was proposed. Based on the preflow, the proposed algorithm chose the lowest label active node as the adjustment point in the selection of active nodes by following the greedy algorithm. The backtracking verification method was introduced to terminate the backtracking loop for enhancing the efficiency of algorithm. The proposed algorithm could meet the demands of various kinds of network graphs and was five more times faster than the classic highest label preflow push algorithm for the sparse networks in the simulation experiments. When applied into the image segmentation, the proposed method achieved more than50 percent of speed compared with the classic algorithm. The proposed lowest label algorithm for minimum cut / maximum flow based on preflow push can satisfy the large-scale network traffic distribution and the image processing of computer vision.