1、1一、树的概念一、树的概念复习复习 第二节第二节 树树2求解方法：求解方法：（1 1）深探法）深探法（2 2）广探法）广探法（3 3）破圈法）破圈法图的生成树不唯一图的生成树不唯一3求解方法：求解方法：（1 1）避圈法）避圈法（2 2）破圈法）破圈法4主要内容主要内容 第三节第三节 最最 短短 路路 问问 题题 5 寻求网络中两点间的最短路就寻求网络中两点间的最短路就是寻求连接这两个点的边的是寻求连接这两个点的边的总权数为最小的道路总权数为最小的道路。（注意：在有向图中，道路（注意：在有向图中，道路中所中所有的弧应是有的弧应是的。）的。）管道铺设、线路安排、厂区布局、管道铺设、线路安排、厂区布
2、局、设备更新等。设备更新等。6从始点出发，逐步从始点出发，逐步顺序顺序地向外探寻地向外探寻，每向外延伸一步都要求是每向外延伸一步都要求是网络中网络中所有的弧权所有的弧权均均 ，即，即 。7：标号标号 P P（永久性标号）（永久性标号）从始点到该标号点的最短路权从始点到该标号点的最短路权。标号标号 T T（试探性标号）（试探性标号）从始点到该标号点的最短路权从始点到该标号点的最短路权。8第一步第一步：始点标上永久标号：始点标上永久标号 P(vP(vS S)=0)=0,其余各其余各点标试探性标号点标试探性标号 T(vT(vj j)=+)=+。第二步：如果第二步：如果v vi i为刚得到为刚得到P
3、P标号的点标号的点,考虑满考虑满足条件足条件(V(Vi i,V,Vj j)E,V)E,Vj j具有具有T T 标号标号;修改修改V Vj j 的的T T标号为标号为9第三步第三步：比较所有具有：比较所有具有T T标号的点标号的点,把最把最小者改为小者改为P P标号标号,即即当存在两个以上最小者时当存在两个以上最小者时,可同时改为可同时改为P P标号标号第二步第二步iv10vvvvvvvv4416769557445P(v)=0T(v)=T(v)=T(v)=T(v)=T(v)=T(v)=T(v)=T(v)=4vvvvvvvv4416769557445T(v)=6P(v)=4;V1P(v3)=6;V
4、1P(v)=0T(v)=T(v)=T(v)=T(v)=T(v)=T(v)=T(v)=T(v2)=4vvvvvvvv4416769557445T(v)=6P(v2)=4;V1)=9T(v5)=8P(v)=6;V1P(v)=0T(v)=T(v)=T(v)=T(v)=T(v)=T(v)=T(v3)=T(v2)=4vvvvvvvv4416769557445T(v)=6P(v2)=4;V1T(v)=9T(v)=8P(V)=8;V2P(v3)=6;V1P(v)=0T(v)=T(v)=T(v)=T(v)=T(v)=T(v)=T(v)=T(v)=4vvvvvvvv4416769557445T(v)=6P(v)
5、=4;V1T(v)=9T(v)=8P(V)=8;V2T(V)=13T(V)=14)=9;V2P(v)=6;V1P(v)=0T(v2)=T(v)=T(v)=T(v)=T(v)=T(v)=)=T(v)=4vvvvvvvv4416769557445T(v)=6P(v)=4;V1T(v)=9T(v)=8P(V)=8;V2T(V)=13T(V)=14P(V)=9;V2P(V)=13;V5P(v)=1P(v)=0T(v)=T(v)=T(v)=T(v)=T(v)=T(v)=T(v)=T(v)=4vvvvvvvv4416769557445T(v)=6P(v)=4;V1T(v)=9T(v)=8P(V)=8;V2
6、T(V)=13T(V7)=14P(V4)=9;V2P(V6)=13;V5T(V)=14T(V)=17P(V)=14;V5P(v3)=1P(v)=0T(v)=T(v)=T(v)=T(v)=T(v)=T(v)=T(v)=T(v)=4vvvvvvvv4416769557445T(v)=6P(v)=4;V1T(v)=9T(v)=8P(V)=8;V2T(V)=13T(V7)=14P(V)=9;V2P(V)=13;V5T(V)=14T(V)=17P(V)=14;V5T(V)=15P(V)=71819 v1v5v3v8v6v4v2v74416769557445T(v2)=4P(v2)=4;V1T(v3)=6
7、P(v3)=6;V1T(v4)=9 T(v4)=9P(v4)=9;V2T(v5)=8T(v5)=8P(v5)=8;V2T(v6)=13T(v6)=13P(v6)=13;V5P(v7)=14;V5T(v7)=14T(v7)=14T(v7)=14P(v1)=0T(v2)=T(v3)=T(v4)=T(v5)=T(v6)=T(v7)=T(v8)=T(v8)=17T(v8)=15P(v8)=15;V721例例2 2：设备更新问题：设备更新问题某工厂使用一台设备，每年年初工厂需要作出决某工厂使用一台设备，每年年初工厂需要作出决定，如果继续使用旧的，要付维修费用；如果购买一定，如果继续使用旧的，要付维修费用
8、；如果购买一台新设备，要付购买费。要求制订一个台新设备，要付购买费。要求制订一个5 5年的更新计划，年的更新计划，目标使总支出最小。目标使总支出最小。22项目第1年 第2年第3年第4年第5年购买费1112131414服役年龄0-11-22-33-44-5维修费5681118残值：对应的是使用n年4321023边边(v(vi i，v vj j)上的数字表示第上的数字表示第i i年初购进设备一直使用年初购进设备一直使用到第到第j j 年年初（年年初（j-1j-1年底）所需要支付的购买、维修年底）所需要支付的购买、维修的全部费用；的全部费用；用用点点v vi i表示第表示第i i年初购进设备，虚设一
9、个年初购进设备，虚设一个V V6 6表示表示第第5 5年年底；年年底；用用边边(v(vi i，v vj j)表示第表示第i i年初购进设备一直使用到第年初购进设备一直使用到第j j 年年年初（年初（j-1j-1年底）；年底）；24v1v6v5v4v3v2v构造图构造图v1v6v5v4v3v2121515141328405919213020294122(v v)=12=11-4（1年的残值）+5(1年维修)(v v)=13=12-4+5；(v,v)=14=13-4+5；(v v)=15=14-4+5；(v v)=15=14-4+5；(v,v)=19=11-3（2年的残值）+5+6(2年维修)(v
10、,v)=28=11-2（3年的残值）+5+6+8(3年维修)(v,v)=40=11-1（4年的残值）+5+6+8+11(4年维修)(v,v)=59=11-0（5年的残值）+5+6+8+11+18(5年维修)(v,v)=20=12-3（2年的残值）+5+6(2年维修)(v,v)=29=12-2（3年的残值）+5+6+8(3年维修)(v,v)=41=12-1（4年的残值）+5+6+8+11(4年维修)(v,v)=21=13-3（2年的残值）+5+6(2年维修)(v,v)=30=13-2（3年的残值）+5+6+8(3年维修)(v,v)=22=14-3（2年的残值）+5+6(2年维修)项目项目第第1年
11、年第第2年年第第3年年第第4年年第第5年年购买购买费费1112131414服役服役年年0-11-22-33-44-5维修维修费费5681118残值残值43210v构造赋权图构造赋权图26v1v6v5v4v3v2121515141328405919213020294122问题转化为求：问题转化为求：从从v v1 1到到v v6 6的最短路问题。的最短路问题。应用应用D D氏标号法求最短路线：氏标号法求最短路线：最短路最短路19+30=4919+30=49；表示表示:在第一年，第三年初各购买一台设备，总费用最小。在第一年，第三年初各购买一台设备，总费用最小。v1v3v627237184566134
12、105275934682练习：用练习：用D D氏标号算法求解从氏标号算法求解从1 1到到8 8的最短路的最短路28237184566134105275934682P1=0T2=T5=T4=T6=T7=T3=T8=29237184566134105275934682min 2,1,3,min 2,1,3,.=1=1，4 4点变点变p p标号标号P1=0T4=T 7=T6=T5=T2=T3=T8=T2=2T4=1T6=3P4=1,v130237184566134105275934682min 2,3,3,min 2,3,3,=2=2，2 2点变点变P P标号标号P1=0T2=T2=25T4=T4=
13、1P4=1,V1T 6=T6=3T 7=T3=T 5=T 8=T 7=3P2=2,v131237184566134105275934682P1=0T2=T2=25T4=T4=1P4=1,v1T 6=T6=3T 7=T3=T 5=T 8=P2=2,v1T3=8T5=7min 3,8,7,3,min 3,8,7,3,=3=3，6 6或或7 7变变P P标号标号T 7=3P6=3,V1P7=3,V432237184566134105275934682P1=0T2=T2=25T4=T4=1P4=1,v1T 6=T6=3T 7=T3=T 5=T 8=P2=2,v1T3=8T5=7T 7=3P6=3,V1
14、P7=3,V4T5=6T8=11P5=6,V7min 8,6,11=6,5min 8,6,11=6,5点点P P标号标号33237184566134105275934682P1=0T2=T2=25T4=T4=1P4=1,v1T 6=T6=3T 7=T3=T 5=T 8=P2=2,v1T3=8T5=7T 7=3P6=3,V1P7=3,V4T5=6T8=11P5=6,V7T8=10P3=8,V2min 10,8=8min 10,8=8，3 3点点P P标号标号34237184566134105275934682P1=0T2=T2=25T4=T4=1P4=1,v1T 6=T6=3T 7=T3=T 5
15、=T 8=P2=2,v1T3=8T5=7T 7=3P6=3,V1P7=3,V4T5=6T8=11P5=6,V7T8=10P3=8,V2min 10,11=10min 10,11=10，8 8点点P P标号标号P8=10,V535237184566134105275934682P1=0T2=T2=25T4=T4=1P4=1,v1T 6=T6=3T 7=T3=T 5=T 8=P2=2,v1T3=8T5=7T 7=3P6=3,V1P7=3,V4T5=6T8=11P5=6,V7T8=10P3=8,V2P8=10,V51 1到到8 8的最短路径为的最短路径为11，4 4，7 7，5 5，88，长度为，长
16、度为10 10 红线为红线为其他各点最短路各点最短路36371.1.计算步骤：计算步骤：(1)(1)先求出最多一步的最短路先求出最多一步的最短路 ，即权矩阵。，即权矩阵。(2)(2)继续求解，继续求解，m=1,2,3,nm=1,2,3,n(3)(3)当当 停止迭代，结果为任意两点停止迭代，结果为任意两点之间的最短距离。之间的最短距离。)1()()1(DDDmm)()1(mmDD)1(D382.2.例题例题3 3 求图中任意两点之间的最短路求图中任意两点之间的最短路39v最多一步的最短路044240628203221005215054321)1(VVVVVD v1 v2 v3 v4 v540v最
17、多两步的最短路04426403625203226605621400442406282032210052150044240628203221005215054535241/3145524125343231255453/132145141332)1()1()2(DDDv1 v2 v3 v4 v5v1 v2 v3 v4 v5V1到各点最多到各点最多1步最短路步最短路各点到各点到V1最多最多1步最短路步最短路各点到各点到V2最多最多1步最短路步最短路V1V2V1 V3 V2V4V5V1V2V1 V3 V1V4V5V1V2V1 V3 V3V4V5V1V2V1 V3 V4V4V5V1V2V1 V3 V5V
18、4V54104426403625203226605621400442406282032210052150044240628203221005215054535241/3145524125343231255453/132145141332)1()1()2(DDDV1V2V2 V3 V1V4V5V1V2V2 V3 V3V4V5V1V2V2 V3 V4V4V5V1V2V2 V3 V5V4V54204426403625203226605621400442406282032210052150044240628203221005215054535241/314513524125343231255453/1
19、32145141332)1()1()2(DDDV1V2V3 V3 V1V4V5V1V2V3 V3 V2V4V5V1V2V3 V3 V4V4V5V1V2V3 V3 V5V4V543v最多三步的最短路04426403625203226605621400442406282032210052150044264036252032266056214054535241/3145524125343231255453/132145/32514133254535241/3145141332)1()2()3(DDDV1V2V1 v2 V3 V2V4V5V1V2V1 v3 V3 V2V4V5V1V2V1 v1 V3
20、V3V4V5V1V2V1 v3 V3 V3V4V5V1V2V1 v1 V3 V4V4V5V1V2V1 v4 V3 V4V4V5V1V2V1 v2 V3 V5V4V5V1V2V1 v4 V3 V5V4V5V1V2V1 v5 V3 V5V4V54404426403625203226605621400442406282032210052150044264036252032266056214054535241/314513524125343241255453/13214514133254535241/31)1()2()3(DDDV1V2V5 v1 V3 V1V4V5V1V2V5 v3 V3 V1V4V
21、5V1V2V5 v4 V3 V1V4V5V1V2V5 v2 V3 V2V4V5V1V2V5 v5 V3 V2V4V5V1V2V5 v3 V3 V3V4V5V1V2V5 v4 V3 V4V4V5V1V2V5 v5 V3 V4V4V5V1V2V5 v5 V3 V3V4V545044264036252032266056214054535241/314513524125343241255453/132145/325141332)2()3(DD已经收敛。最多经过已经收敛。最多经过n n步计算，必然收敛，否步计算，必然收敛，否则有负圈存在（对角线元素出现负值）。则有负圈存在（对角线元素出现负值）。46 某
22、地区的交通网络如图所示，其中点代表居民某地区的交通网络如图所示，其中点代表居民小区，边代表公路，小区，边代表公路，L Lijij代表距离，问中心医院应建代表距离，问中心医院应建在那个小区，可使离医院最远的小区居民就诊时所在那个小区，可使离医院最远的小区居民就诊时所走的路线最近？走的路线最近？例例4 4：服务网点的设置问题：服务网点的设置问题 问题的提法：在交通网络中建立一个中心（可问题的提法：在交通网络中建立一个中心（可以为一学校，医院，消防队以为一学校，医院，消防队，购物中心或厂址选择购物中心或厂址选择等问题）。等问题）。要求要求:该中心选择在何处，使得到的服务最大。该中心选择在何处，使得到
23、的服务最大。)，v1v5v4v3v6v2v720302515206030181548v v v v v v vv0 30 50 63 93 45 60 93v30 0 20 33 63 15 30 63v50 20 0 20 50 25 40 50v63 33 20 0 30 18 33 63v93 63 50 30 0 48 63 93v45 15 25 18 48 0 15 48v60 30 40 33 63 15 063由于由于49思考题思考题:选择中心点问题：选择中心点问题：如果准备在上述小区建立如果准备在上述小区建立2 2所医院，如何选所医院，如何选址？址？50总结：总结：1、求最短路方法：、求最短路方法：和和。2、最短路的应用。、最短路的应用。作业：作业：8.4,8.5,8.6
