网络最大流算法的性能分析

作者：孙小军; 王志强; 刘三阳

来源：数学的实践与认识, 2013, (17): 120-124.

• 最大流
• 动态规划
• 增载轨算法
• 性能分析
• 容量网络 maximum flow
• dynamic programming
• augmenting path algorithm
• performance analysis
• capacity network

对网络最大流问题的求解算法进行性能分析和比较.结果表明,与经典的增载轨算法相比,基于动态规划思想的算法将最大流的求解过程看作一个动态调整过程,通过判断在各个动态阶段各节点允许通过的最大流量,从而能更快的得到网络的最大流值.同时文中的算法分析进一步为这一算法建立了严格的理论基础.

• 单位
  宝鸡文理学院; 西安电子科技大学