-
题名基于重置顶点下标的网络最大流算法
被引量:2
- 1
-
-
作者
罗甜甜
赵礼峰
-
机构
南京邮电大学理学院
-
出处
《计算机技术与发展》
2020年第10期26-30,共5页
-
基金
国家自然科学基金(61304169)。
-
文摘
通过分析最短增广链算法中好的一面是对顶点分层的理念,不足之处在于需要反复构建分层剩余网络造成算法步骤的繁琐,并且在构建了比原网络更轻易发现增广链的分层剩余网络后,在选取增广链时还是存在随机性,这就导致了某些增广链的丢失,使得最终流值偏小的结果。针对这一现象,提出了一种重置顶点下标的最大流改进算法。该算法首先根据每个顶点在整个网络图中所处位置的重要程度制定相应规则,然后对顶点下标按照此规则重新编号,使得网络图更加清晰直观,从而避免了最短增广链算法中反复构造分层剩余网络图的缺陷。而且新算法还增加了寻找增广链的方法用以规避随机性的缺陷,这也为后面寻找增广链有规可循节约了时间。最后通过数值实例仿真实验证明了新算法的简易性和准确性。
-
关键词
最大流
顶点层数
源弧容量
汇弧容量
顶点容差
-
Keywords
maximum flow
vertex layer number
source arc capacity
arcing capacity
vertex tolerance
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
-
题名包含交叉顶点的最大流改进算法
被引量:1
- 2
-
-
作者
罗甜甜
赵礼峰
-
机构
南京邮电大学理学院
-
出处
《计算机工程》
CAS
CSCD
北大核心
2020年第11期48-52,共5页
-
基金
国家自然科学基金(61304169)。
-
文摘
最短增广链算法构建分层剩余网络后,在面临多条相同弧数增广链且其中顶点有重合的情况下,会因寻找增广链时未考虑增广顺序而导致流值丢失。针对该问题,提出一种网络图中包含交叉顶点的最大流改进算法。该算法保留最短增广链算法的分层理念,仍在分层剩余网络中寻找增广链,在此基础上增加寻找增广链的规则,即优先搜索与源点关联且容差最小的顶点作为下一步推进点,确定一条增广链后即考虑与上一条有重合的顶点所在的增广链进行增广。实例分析与BA无标度网络建模仿真结果表明,与最短增广链算法相比,该算法得到的最大流值更准确,并且效率相当。
-
关键词
最大流
分层剩余网络
交叉顶点
顶点容差
BA无标度网络
-
Keywords
maximum flow
hierarchical residual network
intersecting vertice
vertice tolerance
BA scale-free network
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-