求最小费用最大流的改进标号法

An Improved Labeling Method for Minimal Cost Flow

针对现有网络最小费用最大流算法存在的针对性差、步骤繁复、计算量大的问题,根据赋权有向图的最短路算法,提出并证明了一种寻找最小费用增广链的改进标号法。此方法可以直接在网络图上使用,避免了传统方法中需要反复将网络图转化为赋权有向图的操作。将此方法应用到求网络最小费用最大流的计算中,可以简化计算过程,提高运算效率。

To solve the problem of poor targeting, complicated steps, and large computing in traditional algorithm of minimal cost flow, an improved labeling method for minimal cost flow is put forward based on the shortest path algorithm. According to the method, minimal cost augmenting chain can be found directly in the network. The application of the method is simple and intuitive, which avoids the repeatedly conversion from network to weighted diagraph in traditional methods. In other words, it simplifies the calculation process and improves the efficiency of the operation.