最小费用最大流中如何判断有无最短路

Question

如题所述

Answer 1

一．Ford和Fulkerson迭加算法.基本思路：把各条弧上单位流量的费用看成某种长度,用求解最短路问题的方法确定一条自V1至Vn的最短路;在将这条最短路作为可扩充路,用求解最大流问题的方法将其上的流量增至最大可能值;而这条最短路上的流量增加后,其。