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

Abstract

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.