基于宽度优先的网络最大流求解算法

摘要

网络最大流问题是经典的组合优化问题,为了降低求解大规模网络最大流的计算量,若用Ford-Fulkerson算法寻找增广链,则效率不高且步骤繁杂.为了改善以上不足,在原有算法的基础上作了一些改进,应用图的宽度优先搜索原理,针对单源单汇网络提出了一种新的求解最大流问题的算法.该算法的思想是:用宽度优先搜索原理,寻找一条包含剩余容量最大的弧的最短增广链后,删除饱和弧,且沿合适的路径修复包含剩余容量最大的弧的最短增广链.该算法避免了Ford-Fulkerson算法的标号过程,减少了反复重新寻找增广链的次数,为在大规模网络中快速获取最大流的求解提供了方便并提高了求解网络最大流的执行效率.通过实例分析与BA无标度网络建模仿真,验证了该算法的实用性,且新算法的运行效率高于Ford-Fulkerson算法.