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

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

求解最大流问题的“构造式”算法

在前向推进最大流算法的基础上作了改进,提出一种求解最大流问题的“构造式”算法。该算法应用图的深度优先搜索原理,摒弃前向推进最大流算法的并行控制而着眼于每一支流的依次增广,逐步构造中间过程“构造图”的结构并最终得到网络最大流。该方法增强了算法的直观性和可控性,易于实现。