5.图及网络优化.ppt

第十章 图与网络优化 第一节 图的基本概念 二、基本概念 三、基本定理 第二节 树 支撑树的求解方法 四、最小支撑树 四、最大流最小截集的标号法举例 第五节 最小费用最大流问题 二、算法的理论基础 1. 若 f 是流量为 v( f ) 的所有可行流中费用最小者，而 ? 是关于 f 的所有增广链中费用最小的增广链，那么沿? 去调整 f ，得到的可行流 f ’ ，就是流量为v( f ’)的所有可行流中的最小费用流。这样，当f ’ 是最大流时,也就得到了我们所要的最小费用最大流。 三、求解方法 S2：构造赋权有向图W（f（i））：顶点为网络D的顶点，把D中的每条弧(vi , vj)变成方向相反的两条弧(vi , vj) , (vj , vi) ，定义W（f（i））中弧的权为： S3：求W（f（i））起点到终点的最短路，对与这条最短路相应的增广链进行调整。转S2，直到不存在最短路。 v1 v2 vs v3 vt (0, 10) (0, 8) (0, 2) (0, 10) (0, 5) (0, 7) (0, 4) 解： （1）取f（0）= 0为初始可行流。如下图所示，弧旁数字为( fij , cij )。 v1 v2 vs v3 vt 4 1 6 3 2 1 2 构造赋权有向图W（f（0）），用标号法求其最短路。 (vs, 1) (0,0) v1 v2 vs v3 vt 3 1 (vs, 1) (0, 0) (v2, 3) 2 2 1 4 6 v1 v2 vs v3 vt 3 1 (vs, 1) (0, 0) (v2, 3) (v2, 4) 4 1 2 2 6 v1 v2 vs v3 vt 3 1 (vs, 1) (0, 0) (v2, 3) (v2, 4) (v1,4) 6 2 2 1 4 由此得到从vs到vt的最短路： v1 v2 vs v3 vt (4, 10) (1, 8) (6, 2) (3, 10) (2, 5) (1, 7) (2, 4) (vs, 1) (v2, 3) (v1,4) v1 v2 vs v3 vt (0, 10) (0, 8) (0, 2) (0, 10) (0, 5) (0, 7) (0, 4) 与上述最短路相应的增广链为μ＝( vs, v2, v1, vt )。以 ? =5调整该增广链，得到流 f（1），过程如下图所示： (5, 8) (5, 5) (5, 7) 第四步： v1 v2 v3 v4 v5 v6 v7 v8 v9 1 3 2 2 1 6 6 10 4 10 4 2 3 2 3 6 (0,0) (v1,3) (v1,1) (v3,5) (v2,6) 第五步： (v5,9) v1 v2 v3 v4 v5 v6 v7 v8 v9 1 3 2 2 1 6 6 10 4 10 4 2 3 2 3 6 (0,0) (v1,3) (v1,1) (v3,5) (v2,6) 第六步： (v5,9) v1 v2 v3 v4 v5 v6 v7 v8 v9 1 3 2 2 1 6 6 10 4 10 4 2 3 2 3 6 (0,0) (v1,3) (v1,1) (v3,5) (v2,6) (v5,10) 第七步： (v5,12) (v5,9) v1 v2 v3 v4 v5 v6 v7 v8 v9 1 3 2 2 1 6 6 10 4 10 4 2 3 2 3 6 (0,0) (v1,3) (v1,1) (v3,5) (v2,6) (v5,10) v1到v8的最短路为(v1,v3,v2,v5,v8), 其长度为12. v1 v2 v3 v4 v5 v6 v7 v8 v9 1 3 2 2 1 6 6 10 4 10 4 2 3 2 3 6 (v1,1) (v4,11) (v5,10) (v5,9) 优点：能找出从v1到所有点的最短路 缺点：不能解决带有负权的图的最短路问题 (v5,12) (v2,6) (v3,5) (0,0) (v1,3) 情形二：赋权有向图中存在具有负权的弧 v1 v2 v3 v4 v5 v6 v7 v8 例2 求 v1 到图中其他各点的最短路。 6 -1 -2 8 3 -3 -5 -1 2 1 1 1 2 -1 -3 -5 7 (0,0) (v1,-1) (v1,3) (v1,-2) (v1,?) (v1,?) (v1,?) (v1,?) ① v1 v2 v3 v4 v5 v6 v7 v8 6 -1 -2 8 3 -3 -5 -1 2 1 1 1 2 -1 -3 -5 7 (0,0) (v1,-1) (v1,3) (v1,-2) (v1,?) (v1