熊伟编《运筹学》Ch6网络模型.ppt

哥尼斯堡七桥问题 点和线画出各种各样的示意图 图的意义 用G=（V，E） 表示 其中V表示图G的全部顶点的集合 E表示图G的全部边的集合 无向图中的基本概念 点与边 每一条边和两个节点关联，一条边可以用两个节点的标号表示（i，j） 有向图中的基本概念 点与弧（有向边) 每一条弧和两个节点关联，一条弧可以用两个节点的标号表示（i，j） 如果一个有向图D中存在权为负数的回路(称为负回路) ，这样两点间最短路的长度就没有下界。 设给定有向图D=(V,E)及E上的权函数w(e) 以wj表示从vi到vj的最短路的权, w=(vi,vj)仍简记为wij.又设V的点数为n,易知w1, w2, wn,必须满足如下方程: wj =min{ wi+wij}, (vj∈V j=1,2,……n) 对一切i规定wii=0, 若V中的两点vi和vj之间无弧相连,则令w=(vi,vj)=+∞,这样便可认为,任何两点之间都有弧相连了. 开始令wj(0)= w1j(j=1,2,……n),一般地,设已有各个wj(k-1),则: wj(k)= min{ wi(k-1)+ wij} (j=1,2,……n) 当过程进行到某一步,发现每个j都有wj(k)= wj(k-1)时,则计算停止,此时wj(k)就是从vi到vj的最短路的权. 上述算法最多经过n-1次迭代必定收敛。若在已算出的wj(n-1)中至少有某个j,使得wj(n-1)≠wj(n-2), 说明图中有负回路，无最短路. 求解过程可在表上进行。表的左边是初始数据，右边是各次迭代的计算结果，最右边的一列数字就是从V1到各个VJ的最短路的权。 求Wj(0) Wj(0) = W1j W11 = 0 W12 = 2 (1,2) W13 = 3 (1,3) W14 = ∞ W15 = ∞ 求Wj(1) Wj(1) = min {Wi(0) + Wij } W1(1) = min {W1(0) + W11、 W2(0) + W21… W5(0) + W51} = min{0+0、2+2、3-2}=0 W2(1) = min {W1(0) + W12、 W2(0) + W22… W5(0) + W52} = min{0+2、2+0、3-4}=-1（3，2） W3(1) = min {W1(0) + W13、 W2(0) + W23… W5(0) + W53} = min{0+3、3+0}=3（1，3） W4(1) = min {W1(0) + W14、 W2(0) + W24… W5(0) + W53} = ∞ W5(1) = min {W1(0) + W15、 W2(0) + W25… W5(0) + W55} = min{2-2}=0（2，5） 求Wj(2) Wj(2) = min {Wi(1) + Wij } W1(2) = min {W1(1) + W11、 W2(1) + W21… W5(1) + W51} = min{0+0、-1+2、3-2}=0 W2(2) = min {W1(1) + W12、 W2(1) + W22… W5(1) + W52} = min{0+2、-1+0、3-4、0+3}=-1（3，2） W3(2) = min {W1(1) + W13、 W2(1) + W23… W5(1) + W53} = min{0+3、3+0、0+7}=3（1，3） W4(2) = min {W1(1) + W14、 W2(1) + W24… W5(1) + W53} = min{0+4}=4（5，4） W5(2) = min {W1(1) + W15、 W2(1) + W25… W5(1) + W55} = min{-1-2、0+0}=-3（2，5） 求Wj(3) Wj(3) = min {Wi(2) + Wij } W1(3) = min {W1(2) + W11、 W2(2) + W21… W5(2) + W51} = min{0+0、-1+2、3-2、4+5}=0 W2(3) = min {W1(2) + W12、 W2(2) + W22… W5(2) + W52} = min{0+2、-