(4,6,2)
v2
(2,3,0) (2,2,2)
再求v0到vn的最短增流路v0v2v3v1v4vn，路长为 14，可增加1单位的流值。（v3v1反向弧，同 最大流处理）
v1
(4,3,2)
v4 (2,5,3) vn (9,3,0) v5 (3,4,2)
(3,3,3)
v0
(2,2,1) v3
(1,1,1)
b
17,3 (c )
c
（4）在 sbct 路中，每边的容量减 5， wsb ，如图 d。求最小费 用通路 sabct， 单位流费用和为 4 (2) 3 2 7, f0 3 ， 边 ( c, t ) 饱 和。
s
0,
12, 4
a
13,6
0,
t
3, 2
11, 2
b
v1
(4,3,0)
v4 (2,5,0) vn
(3,3,0)
v0
(2,2,0) v3
(1,1,0)
(4,6,0)
v2
(2,3,0) (2,2,0)
(9,3,0) v5
(3,4,0)
(单位运费，边容量，流值）
v1
(4,3,0)
v4 (2,5,0) vn (9,3,0) v5 (3,4,0)
(3,3,0)
s
0,
b
9, 4
8, 2
a
0,
t
0,
13, 6
9, 3
(e)
c
s
16
6
8
a
0
14
t
8
b
8
c
(f)
实际问题实例：一个工厂要将产品送 到火车站，可以有许多道路供其选择，在 不同路线上每吨货物的运费并不相同，而 且每条路线只能有限重量的货物运输，那 么要将w吨的产品从工厂送到火车站，用 什么方法可以使运费最少？
(4,6,0)
v2
(2,3,0) (2,2,0)
将各弧的单位运费作为长度，求v0到vn的最短 增流路v0v1v3v4vn，路长为8，可增加1单位的 流值。
v1
(4,3,0)
v4 (2,5,0) vn (9,3,0) v5 (3,4,0)Leabharlann (3,3,0)v0
(2,2,0) v3
(1,1,0)
(4,6,0)
(4,6,3)
v2
(2,3,1) (2,2,2)
再求v0到vn的最短增流路v0v2v3v1v4vn，路长为 14，可增加1单位的流值。（v3v1反向弧，同 最大流处理）
v1
(4,3,3)
v4 (2,5,4) vn (9,3,0) v5 (3,4,2)
(3,3,3)
v0
(2,2,0) v3
(1,1,1)
(4,6,2)
v2
(2,3,0) (2,2,2)
再求v0到vn的最短增流路v0v2v3v1v4vn，路长为 14，可增加1单位的流值。（v3v1反向弧，同 最大流处理）
v1
(4,3,2)
v4 (2,5,3) vn (9,3,0) v5 (3,4,2)
(3,3,3)
v0
(2,2,1) v3
(1,1,1)
v0
(2,2,0) v3
(1,1,0)
(4,6,0)
v2
(2,3,0) (2,2,0)
将各弧的单位运费作为长度，求v0到vn的最短 增流路v0v1v3v4vn，路长为8，可增加1单位的 流值。
v1
(4,3,0)
v4 (2,5,0) vn (9,3,0) v5 (3,4,0)
(3,3,0)
v0
(2,2,0) v3
s
16,1
15, 4 11, 2
a
14,1
t
8, 2
13, 6
b
17,3
(a)
c
2） 在上述最小费用通路中的每边的 cij 中减去 11， 去掉边 (b, a ) ， 作反向边 (a, b) ，且 c(a, b) f0 , w(a, b) 2 ，如图 b。
wsa wst 5, f0 3 ， 在新网络中求最小费用通路 sat， 边 (a, t ) 饱和。
v2
(2,3,0) (2,2,0)
将各弧的单位运费作为长度，求v0到vn的最短 增流路v0v1v3v4vn，路长为8，可增加1单位的 流值。
v1
(4,3,0)
v4 (2,5,1) vn (9,3,0) v5 (3,4,0)
(3,3,1)
v0
(2,2,1) v3
(1,1,1)
(4,6,0)
v2
(2,3,0) (2,2,0)
v1
(4,3,0)
v4 (2,5,1) vn (9,3,0) v5 (3,4,0)
(3,3,1)
v0
(2,2,1) v3
(1,1,1)
(4,6,0)
v2
(2,3,0) (2,2,0)
再求v0到vn的最短增流路v0v1v4vn，路长为9， 可增加2单位的流值。
v1
(4,3,0)
v4 (2,5,1) vn (9,3,0) v5 (3,4,0)
(4,6,2)
v2
(2,3,0) (2,2,2)
再求v0到vn的最短增流路v0v2v3v1v4vn，路长为 14，可增加1单位的流值。（v3v1反向弧，同 最大流处理）
v1
(4,3,3)
v4 (2,5,4) vn (9,3,0) v5 (3,4,2)
(3,3,3)
v0
(2,2,0) v3
(1,1,1)
0 fij uij , (i, j) A .
注：(1)如果 v( f ) 最大流 v( f max ) ，则本问题就是最小费用最 大流问题。 (2)如果 v( f ) v( f max ) ，则本问题无解。
求最小费用流的算法—迭代法 这里所介绍的求最小费用流的方法叫做迭代法。 这个方法是由 Busacker 和 Gowan 在 1961 年提出的。其主要步骤如下： (i)求出从发点到收点的最小费用通路 P( s, t ) ， 记该通路的边集 合为 E ( P ) 。 (ii)对 P( s, t ) 分配最大可能的流量： f0 min{c( x, y) | ( x, y) E( P)}； 对所有的 ( x, y) E ( P) ，令 c( x, y) c( x, y) f0 ； 对 P( s, t ) 上的饱和边， 其单位流费用相应改为 ， 且当 x 或 y s 或 t 时，将该 P( s, t ) 上的饱和边 ( x, y ) 变为反向边 ( y , x ) 。令 c( y, x) f0 ， w( y, x) w( x, y) (iii)在这样构成的新网络中，重复上述步骤(i)，(ii)，直到从发 点到收点的全部流量等于 为止（或者再也找不到从 s 到 t 的最小 费用道路） 。此时为最小费用最大流。
(3,3,3)
v0
(2,2,1) v3
(1,1,1)
(4,6,2)
v2
(2,3,0) (2,2,2)
再求v0到vn的最短增流路v0v2v5vn，路长为9， 可增加2单位的流值。
v1
(4,3,2)
v4 (2,5,3) vn (9,3,0) v5 (3,4,2)
(3,3,3)
v0
(2,2,1) v3
(1,1,1)
(4,6,2)
v2
(2,3,0) (2,2,2)
再求v0到vn的最短增流路v0v2v3v1v4vn，路长为 14，可增加1单位的流值。（v3v1反向弧，同 最大流处理）
v1
(4,3,2)
v4 (2,5,3) vn (9,3,0) v5 (3,4,2)
(3,3,3)
v0
(2,2,1) v3
(1,1,1)
例 求下图网络中的最小费用流。图中每边上第一个数字是容量 c(i , j ) cij ，第二个数字是单位流费用 w(i, j) wij
s
16,1
15, 4 11, 2
a
14,1
t
8, 2
13, 6
b
17,3
c
解： （1）求 s 到 t 的最小费用通路 sbat，如图 a。单位费用和 wsb wba wat 1 2 1 4 。 本路径中可分配的最大流 f 0 11。边 (b, a ) 饱和。
(4,6,0)
v2
(2,3,0) (2,2,0)
再求v0到vn的最短增流路v0v1v4vn，路长为9， 可增加2单位的流值。
v1
(4,3,2)
v4 (2,5,3) vn (9,3,0) v5 (3,4,0)
(3,3,3)
v0
(2,2,1) v3
(1,1,1)
(4,6,0)
v2
(2,3,0) (2,2,0)
12,3
(d )
c
（5）在 sabct 路中，每边的容量减 3， wsb ，如图 e。在 e 中 再也找不到 s 到 t 的最小费用通路，算法结束。
s
0,
9, 4
8, 2
a
0,
t
0,
13, 6
b
9, 3
c
(e)
综合以上结果，网络中流的分配如图 f。 于是从 s 到 t 的流为： Val f 11 3 5 3 22 最小费用为： 6 4 14 1 16 1 8 2 8 2 8 3 0 6 110
最小费用最大流
前面介绍了一个网络上最大流的算法， 但是还没有考虑到网络 上流的费用问题，在许多实际问题中，费用的因素很重要。例如， 在运输问题中， 人们总是希望在完成运输任务的同时， 寻求一个使 总的运输费用最小的运输方案。 这就是下面要介绍的最小费用流问 题。 在运输网络 N (V , E, c, s, t ) 中，设 w(i, j ) 、 c(i, j ) 、 f (i, j ) 分 别表示边 (i, j ) 的单位流费用、容量和流量， Val f 。所谓最小 费用流问题就是从发点到收点怎样以最小费用输送一已知量为 Val f 的总流量。