(2, 3)
(-4,3) V2 V3 (4,3)
在赋权 图 W(f (3)) 上求出 最短路
求最小费用最大流算法
(4,2) (-4,2) Vs (-2, 5) (-1, 8) V1 (-1,7) (-1,5) (6, 0) Vt
(2, 3)
(-4,3) V2 V3 (4,3)
在初始 赋权图 W(f (0)) 上求出 最短路
(2, 4)
V2
(4,4)
V3
在最短 路上增 加流量 =1 得新的 流量 f (4) =11
求最小费用最大流算法
V1 (4,3) (1,7)
Vt
(2, 4) 5-1 (6, 0)
(2, 4)
(1, 8)
*注意 在负向 弧上减 去增量 值
V2
(4,4)
V3
求最小费用最大流算法
(4,2) (-4,2) Vs (-2, 5) (-1, 8) (6, 0) V1 (-1,7) Vt
上一次 的赋权 图
**依据新 流量在最 短路径上 对此重求 赋权值
(2, 3)
(-4,3) V2 V3 (4,3)
求最小费用最大流算法
bij (-1,7) (4,3) bij w ji 10 Vs (6, (2, 4) 0) 5 (1, 8)
b( f ) b( f )
'
b

ij
bij

此为增广链μ的费用. 最小费用最大流的求解

构造赋权有向图w(f), 定义:
wij w ji bij bij f ij cij f ij cij f ij 0 f ij 0
V1
(4,0)
(1, 0) 7-0
Vt
Vs
(2, 0) (6, 0) 5 - 0 最小 (2, 0)
(1, 0) 8-0
求 增 加 的 流 量
f (0)
V2
(4,0)
V3
求最小费用最大流算法
V1 (4,0) Vs (2, 5) (1, 5)
(1,5)
Vt
(6, 0)
(2, 0)
V2
*只对增广链
V2
(4,0)
V3
求最小费用最大流算法
(4,2) (-4,2) Vs (-2, 5) (-1, 5) (4,0) V3 (6, 0) V1 (-1,7) Vt
(2, 0)
新 赋 权 图 W(f (2))
*只对增广链
V2
求最小费用最大流算法
(4,2) (-4,2) Vs (-2, 5) (-1, 5) (4,0) V3 (6, 0) V1 (-1,7) Vt
Vs
V2
V3
依据新 的流量 构造又 一赋权 图 W(f (1))
*只对增广链
求最小费用最大流算法
V1 (1,5) Vt (2, 5) (-1, 5) 8 V2 (6, 0)
(4,0)
Vs
(2, 0)
赋 权 图 W(f (1)) 的构造
*只对增广链
(4,0)
V3
求最小费用最大流算法
V1 (4,0) Vs (2, 5) 5 (1,5)
5.最小费用最大流
定义: 对D=(V,A,C), 给定一个单位流量 的费用bij≥0, 最小费用最大流即:求一最大 流f, 使
min b( f )
ij ij ( vi , v j ) A
b
f
对增广链μ, 若调整流量θ=1, 那么新可行 流f’的费用比原可行流f的费用增加:
例：用MS-Excel求解网络最大流问题，请 单击问题求解
求最小费用最大流算法
V1
bij wij Vs (2, 0) bij w ji (1, 0)
(1, 0)
f ij cij
(4,0)

Vt
(6, 0)
f ij cij f ij 0 (2, 0) f ij 0
V2
(4,0)
V3
取初始 可行流 f (0) =0 构造赋 权图 W(f (0))
(4,0)
V3
在最短 路上增 加流量 =5 得到新 的流量 (1) f =5
求最小费用最大流算法
V1 (1,5) f ij cij bij wij f ij cij (4,0) Vt f ij 0 bij w ji 0) f ij 0 (2, 5) (6, (2, 0) (1, 5) 8 (4,0)
*只对增广链
求最小费用最大流算法
(4,2) (-4,2) Vs (-2, 5) (-1, 8) V1 (-1,7) (-1,5) (6, 0) Vt
(2, 3)
(-4,3) V2 V3 (4,3)
赋 权 图 W(f (3)) 的构造 *只对增广链
求最小费用最大流算法
(4,2) (-4,2) Vs (-2, 5) (-1, 8) V1 (-1,7) (-1,5) (6, 0) Vt
V1 (1,5)
(0) ij
min{ min (cij f
(4,0)
Vs


), min (f

(0) ij
Vt )}
( 0 )5) f(2, ij (1) (0) (1, 5) f ij f ij (0) f ij
(6, 0) (vi , v j ) (2, 0)
赋 Vt 权 f ij cij 图 f ij cij (2, 0) 的构造 f ij 0 (2) W( f ) f ij 0
V3
*只对增广链
V2
(4,0)
求最小费用最大流算法
(4,2) V1
(-1,7)
Vt
(-4,2)
Vs
(-2, 5)
(-1, 5)
(6, 0)
(2, 0)
赋 权 图 的构造 W(f (2))
Vs
(6, 0)
(2, 0)
在最短 路上增 加流量
V2
(4,0)
V3
求最小费用最大流算法
V1 (1,7) Vt (2, 5) (1, 5) (6, 0)
(4,2)
Vs
(2, 0)
V2
(4,0)
V3
=2 得到新 的流量 f (2)=7 新的流 量图如 图所示
求最小费用最大流算法
V1 (1,5) (-1,5) (-2, 5) (1, 5) (4,0) V3 (6, 0) Vt
f ij cij (2, 0) f ij cij f ij 0 f ij 0 V3
赋 权 图 的构造 W(f (2))
*只对增广链
求最小费用最大流算法
(4,2) (-4,2) Vs (-2, 5) (-1, 5) V1 (1,7) 7
bij wij (6, 0) bij w ji
V1 wij
f ij cij f ij cij Vt f ij 0 f ij 0
(2, 4)
4
V2
(4,4) 10
V3
依据新 的流量 构造又 一赋权 图 W(f (4))
(4,0)
Vs
(2, 0)
构造的 赋权 图 W(f (1))
*只对增广链
V2
求最小费用最大流算法
V1 (1,5) (-1,5) (-2, 5) (-1, 5) (4,0) V3 (6, 0) Vt
(4,0)
Vs
(2, 0)
在赋 权图 W(f (1)) 上求出 最短路
V2
求最小费用最大流算法
V1 (4,0) 10 - 0 (2, 5) (1, 5) 最小 (1,5) 7-5=2 Vt
( k 1) ij
(vi , v j ) (vi , v j ) (vi , v j )

求最小费用最大流算法
V1 Vt
Vs
V2
V3
初 始 网 络 数 值
求最小费用最大流算法
V1 (1, 7) Vt (2, 5) (1, 8) (6, 2)
(4,10)
Vs
(2, 4)
Vt
f ij cij (2, 0) f ij cij f ij 0 f ij 0 V3
对最短 路上求 新的权 值
求最小费用最大流算法
(4,2)
V1 (1,7) Vt Vs (-4,2)
(1, 5)
(-2, 5) (6, 0) b ij wij bij w ji (4,0) V2
求最小费用最大流算法
V1 (4,0) (-1,5) Vs (1,5) 7 Vt
(-1, 5) 8
(-2, 5) 5
(6, 0)
(2, 0)
赋 权 图 W(f (1)) 的构造
*只对增广链
V2
(4,0)
V3
求最小费用最大流算法
V1 (1,5) (-1,5) (-2, 5) (-1, 5) (4,0) V3 (6, 0) Vt
(6, 0)
(2, 3)
V2
(4,3)
在最短 路上增 加流量 =3 得到新 的流量 (3) f =10
求最小费用最大流算法
(4,2) (-4,2) Vs (-2, 5) (1, 8) 8 V2 V1 (-1,7) (-1,5) (6, 0)
Vt
(2, 3)
4 (4,3) 10 V3
依据新 的流量 构造又 一赋权 图 W(f (3))
bij Vt wij (6, 0) bij w ji (2, 0)