关于最小费用最大流算法的一点改进

求解最小费用最大流的一个算法是先求出其最大流,然后在保持流值不变的前提下修改流,使总的费用逐次减少,直到不能减少为止。为了对流作修改,算法中利用了求最短路的Floyf方法,以判别和寻找最大流f所对应的增量网络N~μ(f)中的负权回路。如果存在这样的负权回路Q(即W~μ(Q)【0),如果存在这样的负权回路,则可对流进行修改,使流值不变而总费用减少;如果不存在这样的负权回路,则已是最小费用最大流。本文试图对用Floyd方法寻找负权回路Q这一问题作一些探讨和改进。