在网络中，若每条边【vi，vj】除容量cij外,还给一个数aij，表示从vi到vj运输单位物资所需支付的费用,则问题便是寻找一个可行流{fij},其流值为给定的数值r*,并使总费用取最小值。这样的可行流称为最小费用流。最小费用流问题可用对应于线性规划的原始算法和对偶算法求解。例如,若对偶算法是：从各边流fij=0和流值r=0的最小费用流开始,如果r<r*，则采用以费用作边长求最短路径的方法寻找关于{fij}的增广链，把{fij}调整为流值r′(r<r′≤r*)的最小费用流，直到流值为r*为止。