基于层弧容量比求解网络最大流  

Solving Network Maximum Flow Based on Layer-Arc Capacity Ratio

作　　者：朱雨 赵礼峰[1] ZHU Yu;ZHAO Lifeng(School of Science,Nanjing University of Posts and Telecommunications,Nanjing 210023,China)

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

出　　处：《电视技术》2020年第6期1-5,共5页Video Engineering

摘　　要：针对最短增广链算法一开始选取增广路径的随意性,给出了一种在单源、单汇网络中通过层弧容量比来求解网络最大流的新算法。该改进算法的思想是运用宽度优先搜索的方法,在改进的分层剩余网络中找到与汇点相邻接且容量最大的弧(称为关键弧),再选择含有关键弧的最短增广路径,根据制定的规则,从而有序地进行流值增广,直至没有可增广的路径终止。在BA无标度网络中进行实验,发现新算法的效率略高于最短增广链算法,且能把关键弧的容量更加合理地分配给上一层弧,提高了最大流的流值。For the arbitrariness of the shortest augmentation chain algorithm at the beginning to choose the augmentation path,a new algorithm for solving the maximum flow of the network through the layer arc capacity ratio in a single source and single sink network is given.The idea of the improved algorithm is to use the breadth-first search method to find the arc with the largest capacity adjacent to the sink in the improved layered residual network,which is called the key arc,and then select the shortest augmentation containing the key arc The path,in accordance with the established rules,increases the flow value in an orderly manner until there is no extendable path to terminate.Experiments in the BA scale-free network show that the efficiency of the new algorithm is slightly higher than that of the shortest augmented chain algorithm,and the capacity of the critical arc can be more reasonably allocated to the upper layer of arc,and the flow value of the maximum flow is finally improved.

关 键 词：最大流 分层 增广路径 关键弧 BA无标度网络 

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