计算机技术与发展2017，Vol.27Issue(8)：88-91,4.DOI:10.3969/j.issn.1673-629X.2017.08.018
基于最短增广链的最大流改进算法
Improved Algorithm of Maximum Flow with Shortest Augmenting Chain
摘要
Abstract
The maximum network flow is a classic combinatorial optimization problem,which mainly consists of Ford-Fulkerson algorithm,the shortest augmenting chain algorithm (Dinic algorithm) and preflow push algorithm.The desired maximum flow from Ford-Fulkerson algorithm could not be acquired because of the arbitrariness when choosing the augmented chain.The shortest augmenting chain algorithm can find the shortest augmenting chain in the remaining layered network to avoid the augmented chain selected arbitrary,however,it needs to search again shortest augmenting chain in maximum flow when augmenting with low using rate.Aimed at this problem,a new shortest augmenting chain repair algorithm is presented.After it has adjusted flow along the shortest augmenting chain the arc of zero flow on the augmented chain has been removed to retain the arc that the flow zero,which select the appropriate nodes to repair shortest augmenting chain in the remaining nodes for improving the efficiency and reducing the times of search shortest augmenting chain.The improved algorithm is verified through the modeling and simulation experimental in BA scale-free network,which shows that its efficiency is higher than the shortest augmenting chain algorithm.关键词
最大流/分层剩余网络/最短增广链/BA无标度网络Key words
maximum flow/remaining layered network/shortest augmenting chain/BA scale-free network分类
信息技术与安全科学引用本文复制引用
赵礼峰,纪亚劲..基于最短增广链的最大流改进算法[J].计算机技术与发展,2017,27(8):88-91,4.基金项目
国家自然科学基金青年基金项目(61304169) （61304169）
