最大流问题的改进最短增广链算法

摘要：

在最大流问题中，由于Ford-Fulkerson算法中增广链选取的任意性，导致该算法不是有效的多项式算法。经典的最短增广链算法是通过在增广过程中寻找最短增广链，从而排除增广链选取的任意性。但计算过程中为寻找最短增广链，需要根据原网络循环地构建剩余网络和剩余分层网络，步骤非常繁杂。为改善以上不足，基于经典最短增广链算法，提出改进最短增广链算法。该算法的思想是：若在增广剩余分层网络中流值的过程中得到饱和弧，则删除该弧对应于原网络中的弧，使原网络得以简化，以此可降低构建剩余网络和剩余分层网络的复杂性，从而优化最短增广链算法。理论和仿真实验都表明，改进算法不仅正确，而且比原算法效率更高。

关键词：最大流、最短增广链、剩余网络、剩余分层网络

所属期刊栏目：26

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金青年基金项目61304169

在线出版日期：2016-09-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：52-54,59