最短路问题实验实用教案

1、会计学1最短路问题最短路问题(wnt)实验实验第一页，共27页。固固 定定 起起 点点 的的 最最 短短 路路最短路是一条(y tio)路径，且最短路的任一段也是最短路 假设在u0-v0的最短路中只取一条，则从u0到其余顶点(dngdin)的最短路将构成一棵以u0为根的树 因此, 可采用(ciyng)树生长的过程来求指定顶点到其余顶点的最短路第1页/共27页第二页，共27页。第2页/共27页第三页，共27页。算法算法(sun f)步骤：步骤：第3页/共27页第四页，共27页。第4页/共27页第五页，共27页。)(iul迭代次数1u2u3u 4u5u6u 7u 8u2345678 0 2 8 1

2、0 8 3 10 8 6 10 12 7 1012 9 12 12最后标记:)(vl)(vz 0 2 1 7 3 6 9 12 1u 1u 1u 6u 2u 5u 4u 5u第5页/共27页第六页，共27页。)(iul1u2u3u 4u5u6u 7u 8u最后标记:)(vl)(vz 0 2 1 7 3 6 9 12 1u 1u 1u 6u 2u 5u 4u 5uu1u2u3u4u5u6u7u8第6页/共27页第七页，共27页。第7页/共27页第八页，共27页。第8页/共27页第九页，共27页。floyd算法算法(sun f)的基本思想的基本思想第9页/共27页第十页，共27页。算法原理算法原理

3、 求距离矩阵求距离矩阵(j zhn)(j zhn)的方法的方法第10页/共27页第十一页，共27页。算法原理算法原理 求路径矩阵求路径矩阵(j zhn)(j zhn)的方法的方法在建立距离(jl)矩阵的同时可建立路径矩阵R 即当vk被插入任何两点间的最短路径时，被记录在R(k)中，依次求 时求得 ，可由 来查找任何点对之间最短路的路径( )D( )R( )R第11页/共27页第十二页，共27页。ij算法算法(sun f)(sun f)原理原理 查找最短路路径的方法查找最短路路径的方法pkp2p1p3q1q2qm则由点i到j的最短路的路径为：jqqqpppimk,21, 12第12页/共27页第

4、十三页，共27页。算法算法(sun f)步骤步骤第13页/共27页第十四页，共27页。5333434331543243332344441,0646960243420256420793570RD第14页/共27页第十五页，共27页。第15页/共27页第十六页，共27页。第16页/共27页第十七页，共27页。一、一、 可化为最短路问题可化为最短路问题(wnt)的多阶段决策问题的多阶段决策问题(wnt)二、二、 选选 址址 问问 题题1、 中心中心(zhngxn)问题问题2、 重心重心(zhngxn)问题问题第17页/共27页第十八页，共27页。第18页/共27页第十九页，共27页。购购置置年年份份

5、12345单位（万元）1111121213使用年数 0-1 1-2 2-3 3-4 4-5维维修修费费用用（万万元元）5681118第19页/共27页第二十页，共27页。第20页/共27页第二十一页，共27页。v1v2v3v4v5v6第21页/共27页第二十二页，共27页。（2） 计算在各点iv设立服务设施的最大服务距离)(ivS max)(1ijjidvS , 2 , 1i 选址问题(wnt)-中心问题(wnt)例例 2某城市要建立一个消防站，为该市所属的七个区服务，如图所示问应设在那个区，才能使它至最远区的路径最短（1）用 Floyd 算法求出距离矩阵 D=)(ijd（3）求出顶点kv，使

6、)(min)(1iikvSvS则kv就是要求的建立消防站的地点此点称为图的中心点中心点第22页/共27页第二十三页，共27页。05 .15 .55 .86475 .10475 .45 .25 .55 .54032475 .8730571065 .42502545 .24720375 .5710530DS(v1)=10, S(v2)=7, S(v3)=6, S(v4)=8.5, S(v5)=7, S(v6)=7, S(v7)=8.5S(v3)=6,故应将消防站设在v3处。 第23页/共27页第二十四页，共27页。 选址(xun zh)问题-重心问题例例 3某矿区有七个矿点，如图所示已知各矿点每天

7、的产矿量)(jvq（标在图的各顶点上） 现要从这七个矿点选一个来建造矿厂 问应选在哪个矿点，才能使各矿点所产的矿运到选矿厂所在地的总运力（千吨公里）最小（1）求距离阵 D=)(ijd（2） 计算各顶点作为选矿厂的总运力)(ivm ijjjidvqvm)()(1 , 2 , 1i（3） 求kv使)(min)(1iikvmvm，则kv就是选矿厂应设之矿点此点称为图 G 的重心重心或中位点中位点第24页/共27页第二十五页，共27页。实验实验(shyn)(shyn)作业作业 可在下面两个(lin )题中任选其一1. 下表为某工程的全部(qunb)工序以及工序时间与 紧前工序，工 序ABCDEFGHIJK工序时间（天）247310243232紧前工序/AAABC,D,KE,FDHG,IB请完成以下问题：1）. 给出工程网络图；2）. 计算完成整个工程至少需要多少天（总工期）。3）. 请问不误总工期的前提下，工程H可否延误？最多能够延误多少天？第25页/共27页第二十六页，共27页。2、选址问题、选址问题 现准备现准备(zhnbi)在