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

A Network Maximum Flow Algorithm Based on Reset Vertex Subscript

作　　者：罗甜甜 赵礼峰[1] LUO Tian-tian;ZHAO Li-feng(School of Science,Nanjing University of Posts and Telecommunications,Nanjing 210023,China)

机构地区：[1]南京邮电大学理学院,江苏南京210023

出　　处：《计算机技术与发展》2020年第10期26-30,共5页Computer Technology and Development

基　　金：国家自然科学基金(61304169)。

摘　　要：通过分析最短增广链算法中好的一面是对顶点分层的理念,不足之处在于需要反复构建分层剩余网络造成算法步骤的繁琐,并且在构建了比原网络更轻易发现增广链的分层剩余网络后,在选取增广链时还是存在随机性,这就导致了某些增广链的丢失,使得最终流值偏小的结果。针对这一现象,提出了一种重置顶点下标的最大流改进算法。该算法首先根据每个顶点在整个网络图中所处位置的重要程度制定相应规则,然后对顶点下标按照此规则重新编号,使得网络图更加清晰直观,从而避免了最短增广链算法中反复构造分层剩余网络图的缺陷。而且新算法还增加了寻找增广链的方法用以规避随机性的缺陷,这也为后面寻找增广链有规可循节约了时间。最后通过数值实例仿真实验证明了新算法的简易性和准确性。By analyzing the positive side of the shortest augmented chain algorithm,the concept of layering the vertices is inadequate because it requires the repeated construction of a layered residual network to cause tedious algorithm steps,and it is easier to find the augmented chain than the original network.After layering the residual network,there is still randomness when selecting the augmented chain,which leads to the loss of some augmented chains,resulting in a small final flow value.Aiming at this phenomenon,an improved maximum flow algorithm for resetting the vertex index is proposed.The algorithm first formulates corresponding rules according to the importance of the position of each vertex in the entire network graph,and then renumbers the vertex subscripts in accordance with this rule,making the network graph more clear and intuitive,thereby avoiding the defects of repetitive construction of hierarchical residual network graphs in the shortest augmentation chain algorithm.In addition,the proposed algorithm also adds a method to find the augmented chain to avoid the shortcomings of randomness,which also saves time for the future to find the regularized and augmented chain.Finally,numerical examples are used to demonstrate the simplicity and accuracy of the proposed algorithm.

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]