Novel two⁃stage preflow algorithm for solving the maximum flow problem in a network with circles  

两阶段预流算法构建及其在带环网络最大流中的应用

作　　者：DANG Yaoguo HUANG Jinxin DING Xiaoyu WANG Junjie 党耀国;黄金鑫;丁孝郁;王俊杰(南京航空航天大学经济与管理学院,南京211100)

机构地区：[1]College of Economics and Management,Nanjing University of Aeronautics and Astronautics,Nanjing 211100,China

出　　处：《Journal of Southeast University(English Edition)》2025年第1期91-100,共10页东南大学学报(英文版)

基　　金：The National Natural Science Foundation of China(No.72001107,72271120);the Fundamental Research Funds for the Central Universities(No.NS2024047,NP2024106);the China Postdoctoral Science Foundation(No.2020T130297,2019M660119).

摘　　要：The presence of circles in the network maximum flow problem increases the complexity of the preflow algorithm.This study proposes a novel two-stage preflow algorithm to address this issue.First,this study proves that at least one zero-flow arc must be present when the flow of the network reaches its maximum value.This result indicates that the maximum flow of the network will remain constant if a zero-flow arc within a circle is removed;therefore,the maximum flow of each network without circles can be calculated.The first stage involves identifying the zero-flow arc in the circle when the network flow reaches its maximum.The second stage aims to remove the zero-flow arc identified and modified in the first stage,thereby producing a new network without circles.The maximum flow of the original looped network can be obtained by solving the maximum flow of the newly generated acyclic network.Finally,an example is provided to demonstrate the validity and feasibility of this algorithm.This algorithm not only improves computational efficiency but also provides new perspectives and tools for solving similar network optimization problems.在处理带环网络的最大流问题时,为了降低算法的复杂度,提出了一种新颖的两阶段预流算法。首先,证明了当网络达到最大流状态时,环中必然存在至少一条最小可能流等于零的弧。在环中,如果每条弧同时获得最小可能流量,在移除任意一条弧之后,环中原始零流弧保持不变。其次,构建了使带环网络转换为无环网络两阶段预流算法:阶段1为当网络达到最大流时标记出环中的零流弧;阶段2为去除在阶段1中找到的零流弧,从而将原本的带环网络转化为无环网络。通过求解新生成的无环网络的最大流,可以得到原始带环网络的最大流解。最后,通过实例验证了该算法的有效性和可行性。该算法不仅提高了计算效率,还为解决类似网络优化问题提供了新的视角和工具。

关 键 词：network with circles maximum flow zeroflow arc two-stage preflow algorithm 

分 类 号：O22[理学—运筹学与控制论] O157.5[理学—数学]