基于重置顶点下标的网络最大流算法

来源：计算机技术与发展杂志2020年第10期北京时间：

作者：罗甜甜;赵礼峰

摘要：通过分析最短增广链算法中好的一面是对顶点分层的理念,不足之处在于需要反复构建分层剩余网络造成算法步骤的繁琐, 并且在构建了比原网络更轻易发现增广链的分层剩余网络后,在选取增广链时还是存在随机性,这就导致了某些增广链的丢失,使得最终流值偏小的结果。 针对这一现象,提出了一种重置顶点下标的最大流改进算法。该算法首先根据每个顶点在整个网络图中所处位置的重要程度制定相应规则,然后对顶点下标按照此规则重新编号,使得网络图更加清晰直观,从而避免了最短增广链算法中反复构造分层剩余网络图的缺陷。 而且新算法还增加了寻找增广链的方法用以规避随机性的缺陷,这也为后面寻找增广链有规可循节约了时间。 最后通过数值实例仿真实验证明了新算法的简易性和准确性。

关键词：最大流;顶点层数;源弧容量;汇弧容量;顶点容差