论文研究-网络最大流的自适应求解算法——SAPR算法.pdf

为提升对大规模不同拓扑结构网络的求解速度，通过评估基本操作的执行效率、动态调整活跃顶点的选择方式及盈余流的推进方式，提出了一种可高效求解多类拓扑网络的自适应预流推进算法——SAPR（self-adaptive push-relabel）算法。在The First DIMACS implementation Challenge提供的七类不同拓扑结构网络上，对SAPR算法及四种适用于特定拓扑网络的算法进行了对比实验，结果表明：SAPR算法在一半的数据上能持平高效的H_PRF算法，而另一半能超越H_PRF算法。SAPR算法的高效性和强稳定性解决了传统算法在多类拓扑网络中不能都取得高效率的问题。