第6章最短路问题课件.ppt

1、PPT课件运运 筹筹 帷帷 幄幄 之之 中中决决 胜胜 千千 里里 之之 外外图与网络分析图与网络分析Graph Theory and Network Analysis Graph Theory and Network Analysis 第六章第六章PPT课件如何用最短的线路将三部电话连起来？如何用最短的线路将三部电话连起来？此问题可抽象为设此问题可抽象为设ABC为等边三角形，连接三顶点的路为等边三角形，连接三顶点的路线（称为网络）。这种网络有许多个，其中最短路线者显然线（称为网络）。这种网络有许多个，其中最短路线者显然是二边之和（如是二边之和（如ABAC）。）。ABCPPT课件ABCP但若增

2、加一个周转站（新点但若增加一个周转站（新点P），连接），连接4点的新网络的最短路点的新网络的最短路线为线为PAPBPC。最短新路径之长。最短新路径之长N比原来只连三点的最比原来只连三点的最短路径短路径O要短。这样得到的网络不仅比原来节省材料，而且要短。这样得到的网络不仅比原来节省材料，而且稳定性也更好。稳定性也更好。PPT课件问题描述：问题描述：就是从给定的网络图中找出一点到各点或任意两点之间就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路距离最短的一条路.有些问题，如选址、管道铺设时的选线、设备更新、投有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划

3、的问题，也可以归结为求最短资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。路的问题。因此这类问题在生产实际中得到广泛应用。PPT课件一老汉带了一只狼、一只羊、一棵白菜想要从南岸过河一老汉带了一只狼、一只羊、一棵白菜想要从南岸过河到北岸，河上只有一条独木舟，每次除了人以外，只能带一到北岸，河上只有一条独木舟，每次除了人以外，只能带一样东西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，样东西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，问应该怎样安排渡河，才能做到既把所有东西都运过河去，问应该怎样安排渡河，才能做到既把所有东西都运过河去，并且在河

4、上来回次数最少？这个问题就可以用求最短路方法并且在河上来回次数最少？这个问题就可以用求最短路方法解决。解决。PPT课件定义：定义：1）人）人M（Man），狼），狼W（Wolf），），羊羊G（Goat），），草草H（Hay）2）点点 vi 表示河岸的状态表示河岸的状态3）边边 ek 表示由状态表示由状态 vi 经一次渡河到状态经一次渡河到状态 vj 4）权权边边 ek 上的权定为上的权定为 1我们可以得到下面的加权有向图我们可以得到下面的加权有向图PPT课件状态说明：状态说明：v1,u1=(M,W,G,H);v2,u2=(M,W,G);v3,u3=(M,W,H);v4,u4=(M,G,H);v5

5、,u5=(M,G)此游戏转化为在下面的二部图中求从此游戏转化为在下面的二部图中求从 v1 到到 u1 的最短路问题。的最短路问题。v1v2v3v4v5u5u4u3u2u1PPT课件求最短路有两种算法求最短路有两种算法:狄克斯屈拉狄克斯屈拉(Dijkstra)标号算法标号算法 逐次逼近算法逐次逼近算法PPT课件若序列若序列 vs,v1.vn-1,vn 是从是从vs到到vn间间的最短路，则序列的最短路，则序列 vs,v1.vn-1 必为从必为从vs 到到vn-1的最短路。的最短路。假定假定v1v2 v3 v4是是v1 v4的最短路，则的最短路，则v1 v2 v3一定是一定是v1 v3的最短路，的最

6、短路，v2 v3 v4也一定是也一定是v2 v4的最短路。的最短路。v1v2v3v4v5PPT课件求网络图的最短路，设图的起点是求网络图的最短路，设图的起点是vs,终点是终点是vt ,以以vi为起点为起点vj为终点的弧记为为终点的弧记为(i,j)距离为距离为dij：b(j)起点起点vs到点到点vj的最短路长；的最短路长；：k(i,j)=b(i)+dij，步骤：步骤：1.令起点的标号；令起点的标号；b(s)0。2.找出所有找出所有vi已标号已标号vj未标号的弧集合未标号的弧集合 B=(i,j)如果这样的如果这样的弧不存在或弧不存在或vt已标号则计算结束；已标号则计算结束；3.计算集合计算集合B中

7、弧中弧k(i，j)=b(i)+dij的标号的标号4.选一个点标号选一个点标号 在终点在终点vl处标处标号号b(l),返回到第返回到第2步。步。,),(|),(min)(Bjijiklbj PPT课件例例6.5 求下图求下图v1到到v7的最短路长及最短路线的最短路长及最短路线862523534210570862254411147510711P标号标号T标号标号9PPT课件v1到到v7的最短路长及最短路线如图所示：的最短路长及最短路线如图所示：86252353421057v7已标号，计算结束。从已标号，计算结束。从v1到到v7的最短路长是的最短路长是 11,最短路线：最短路线：v1 v4 v6 v

8、702411PPT课件从上例知，只要某点已标号，说明已找到起点从上例知，只要某点已标号，说明已找到起点vs到到该点的最短路线及最短距离，因此可以将每个点标该点的最短路线及最短距离，因此可以将每个点标号，求出号，求出vs到任意点的最短路线，如果某个点到任意点的最短路线，如果某个点vj不能不能标号，说明标号，说明vs不可达不可达vj。注：无向图最短路的求法只将上述步骤注：无向图最短路的求法只将上述步骤2将弧改成边即可。将弧改成边即可。PPT课件例例6.6 求下图求下图v1到各点的最短距离及最短路线。到各点的最短距离及最短路线。452617839326121618045223103961264116

9、6188122482418PPT课件v1到各点的最短距离及最短路线如图所示：到各点的最短距离及最短路线如图所示：45261783932612161802618所有点都已标号，点上的标号就是所有点都已标号，点上的标号就是v1到该点的最短距离，最短到该点的最短距离，最短路线就是红色的链。路线就是红色的链。PPT课件237184566134105275934682例例6.7 求从求从1 1到到8 8的最短路径的最短路径PPT课件237184566134105275934682X=1,w1=0min c12,c14,c16=min 0+2,0+1,0+3=min 2,1,3=1X=1,4,p4=1p4

10、=1p1=0PPT课件237184566134105275934682X=1,4min c12,c16,c42,c47=min 0+2,0+3,1+10,1+2=min 2,3,11,3=2X=1,2,4,p2=2p1=0p4=1p2=2PPT课件237184566134105275934682X=1,2,4min c16,c23,c25,c47=min 0+3,2+6,2+5,1+2=min 3,8,7,3=3X=1,2,4,6,p6=3p2=2p4=1p1=0p6=3PPT课件237184566134105275934682X=1,2,4,6min c23,c25,c47,c67=min

11、2+6,2+5,1+2,3+4=min 8,7,3,7=3X=1,2,4,6,7,p7=3p2=2p4=1p1=0p6=3p7=3PPT课件237184566134105275934682X=1,2,4,6,7min c23,c25,c75,c78=min 2+6,2+5,3+3,3+8=min 8,7,6,11=6X=1,2,4,5,6,7,p5=6p2=2p4=1p1=0p6=3p7=3p5=6PPT课件237184566134105275934682X=1,2,4,6,7min c23,c53,c58,c78=min 2+6,6+9,6+4,3+8=min 8,15,10,11=8X=1

12、,2,3,4,5,6,7,p3=8p2=2p4=1p1=0p6=3p7=3p5=6p3=8PPT课件237184566134105275934682X=1,2,3,4,6,7min c38,c58,c78=min 8+6,6+4,3+7=min 14,10,11=10X=1,2,3,4,5,6,7,8,p8=10p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10PPT课件237184566134105275934682X=1,2,3,4,6,7,81 1到到8 8的最短路径为的最短路径为11，4 4，7 7，5 5，88，长度为，长度为1010。p2=2p4=1p1=0p6=3

13、p7=3p5=6p3=8p8=10PPT课件课堂练习：课堂练习：1.用用Dijkstra算法求下图从算法求下图从v1到到v6的最短距离及路线。的最短距离及路线。v3v54v1v2v4v635222421v1到到v6的最短路为：的最短路为：6521vvvvPPT课件2.求下图中求下图中v1点到另外任意一点的最短路径点到另外任意一点的最短路径v1v2v3v4v6v5322762133PPT课件v1V2V3V4 V6V5322762133024714PPT课件v1V2V3V4 V6V5322762133024714PPT课件算法适用条件：算法适用条件：Dijkstra算法只适用于全部权为非负情况，如

14、果某算法只适用于全部权为非负情况，如果某边上权为负的，算法失效。此时可采用逐次逼近边上权为负的，算法失效。此时可采用逐次逼近算法。算法。例例6.7 如右图所示中按如右图所示中按dijkstra算算法可得法可得P(v1)=5为从为从vsv1的最短的最短路长显然是错误的，从路长显然是错误的，从vsv2v1路长只有路长只有3。v2vsv15-58PPT课件例例6.8 设备更新问题。某公司使用一台设备，在每年年初，设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设

15、备的维修费用置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。已知：内购置费用和维修费用总的支付费用最小。已知：设备每年年初的价格表设备每年年初的价格表年份年份12345年初价格年初价格1111121213PPT课件设备维修费如下表设备维修费如下表使用年数使用年数0-11-22-33-44-5每年维修费用每年维修费用5681118解：将问题转化为最短

16、路问题，如下图：用解：将问题转化为最短路问题，如下图：用vi表示表示“第第i年年年年初购进一台新设备初购进一台新设备”,弧（弧（vi,vj）表示第）表示第i年年初购进的设备一年年初购进的设备一直使用到第直使用到第j年年初。年年初。v1v2v3v4v5v6PPT课件把所有弧的权数计算如下表，把所有弧的权数计算如下表，把权数赋到图中，再用把权数赋到图中，再用Dijkstra算法求最短路。算法求最短路。123456116223041592162230413172331417235186v1v2v3v4v5v6162230415916223041312317181723W12=11+5=16W13=1

17、1+5+6=22W14=11+5+6+8=30W15=11+5+6+8+11=41W16=11+5+6+8+11+18=59W23=11+5=16W24=11+5+6=22W25=11+5+6+8=30 W26=11+5+6+8+11=41W34=12+5=17W35=12+5+6=23W36=12+5+6+8=31W45=12+5=17 W46=12+5+6=23W56=13+5=18PPT课件 最终得到下图，可知，最终得到下图，可知，v1到到v6的距离是的距离是53，最短路径有两条：，最短路径有两条：v1v3v6和和 v1v4v6 V1（0,s）v3v4(41,1)v5v62230415916(22,1)3041312317181723 V2（16,1）16(30,1)(53,3)(53,4)PPT课件