第6章最短路问题--课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,PPT课件,单击此处编辑母版标题样式,单击此处编辑母版文本样式,PPT课件,单击此处编辑母版标题样式,单击此处编辑母版文本样式,PPT课件,单击此处编辑母版标题样式,单击此处编辑母版文本样式,PPT课件,单击此处编辑母版标题样式,单击此处编辑母版文本样式,PPT课件,单击此处编辑母版标题样式,单击此处编辑母版文本样式,PPT课件,单击此处编辑母版标题样式,单击此处编辑母版文本样式,PPT课件,运 筹 学,(Operations Research),PPT课件,运 筹 学(Operations Research,运 筹 帷 幄 之 中,决 胜 千 里 之 外,图与网络分析,Graph Theory and Network Analysis,第六章,PPT课件,运 筹 帷 幄 之 中决 胜 千 里 之,最短路问题,如何用最短的线路将三部电话连起来？,此问题可抽象为设,ABC,为等边三角形，连接三顶点的路线（称为网络）。这种网络有许多个，其中最短路线者显然是二边之和（如,ABAC,）。,A,B,C,PPT课件,最短路问题如何用最短的线路将三部电话连起来？ABCPPT课件,最短路问题,A,B,C,P,但若增加一个周转站（新点,P,），连接,4,点的新网络的最短路线为,PA,PB,PC,。最短新路径之长,N,比原来只连三点的最短路径,O,要短。这样得到的网络不仅比原来节省材料，而且稳定性也更好。,PPT课件,最短路问题ABCP但若增加一个周转站（新点P），连接4点的新,最短路问题,问题描述：,就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路,.,有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。,PPT课件,最短路问题问题描述：PPT课件,最短路问题,例,6.4,渡河游戏,一老汉带了一只狼、一只羊、一棵白菜想要从南岸过河到北岸，河上只有一条独木舟，每次除了人以外，只能带一样东西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，问应该怎样安排渡河，才能做到既把所有东西都运过河去，并且在河上来回次数最少？这个问题就可以用求最短路方法解决。,PPT课件,最短路问题例6.4 渡河游戏PPT课件,最短路问题,定义：,1,）人,M,（,Man,），狼,W,（,Wolf,），羊,G,（,Goat,），草,H,（,Hay,）,2,）点,v,i,表示河岸的状态,3,）边,e,k,表示由状态,v,i,经一次渡河到状态,v,j,4,）权,边,e,k,上的权定为,1,我们可以得到下面的加权有向图,PPT课件,最短路问题定义：我们可以得到下面的加权有向图PPT课件,最短路问题,状态说明：,v,1,u,1,=(M,W,G,H);v,2,u,2,=(M,W,G);v,3,u,3,=(M,W,H);,v,4,u,4,=(M,G,H);v,5,u,5,=(M,G),此游戏转化为在下面的二部图中求从,v,1,到,u,1,的最短路问题。,v,1,v,2,v,3,v,4,v,5,u,5,u,4,u,3,u,2,u,1,PPT课件,最短路问题状态说明：此游戏转化为在下面的二部图中求从 v1,最短路问题,求最短路有两种算法,:,狄克斯屈拉,(Dijkstra),标号算法,逐次逼近算法,PPT课件,最短路问题求最短路有两种算法:狄克斯屈拉(Dijkstr,最短路问题,狄克斯屈拉,(Dijkstra),标号算法的基本思路：,若序列,v,s,v,1,.v,n-1,v,n,是从,v,s,到,v,n,间的最短路，则序列,v,s,v,1,.v,n-1,必为从,v,s,到,v,n-1,的最短路。,假定,v,1,v,2,v,3,v,4,是,v,1,v,4,的最短路，则,v,1,v,2,v,3,一定是,v,1,v,3,的最短路，,v,2,v,3,v,4,也一定是,v,2,v,4,的最短路。,v,1,v,2,v,3,v,4,v,5,PPT课件,最短路问题狄克斯屈拉(Dijkstra)标号算法的基本思路：,最短路问题,求网络图的最短路，设图的起点是,v,s,终点是,v,t,以,v,i,为起点,v,j,为终点的弧记为,(i,j),距离为,d,ij,P,标号,(,点标号,),：,b,(j),起点,v,s,到点,v,j,的最短路长；,T,标号,(,边标号,),：,k(,i,j,)=,b,(,i,)+,d,ij,，,步骤：,1.,令起点的标号；,b,(,s,),0,。,2.,找出所有,v,i,已标号,v,j,未标号的弧集合,B=(,i,j,),如果这样的弧不存在或,v,t,已标号则计算结束；,3.,计算集合,B,中弧,k,(,i,，,j,)=,b,(,i,)+,d,ij,的标号,4.,选一个点标号 在终点,v,l,处标号,b(l),返回到第,2,步。,PPT课件,最短路问题求网络图的最短路，设图的起点是vs,终点是vt,最短路问题,例,6.5,求下图,v,1,到,v,7,的最短路长及最短路线,8,6,2,5,2,3,5,3,4,2,10,5,7,0,8,6,2,2,5,4,4,11,14,7,5,10,7,11,P,标号,T,标号,9,PPT课件,最短路问题例6.5 求下图v1到v7的最短路长及最短路线,最短路问题,v,1,到,v,7,的最短路长及最短路线如图所示：,8,6,2,5,2,3,5,3,4,2,10,5,7,v,7,已标号，计算结束。从,v,1,到,v,7,的最短路长是,11,最短路线：,v,1,v,4,v,6,v,7,0,2,4,11,PPT课件,最短路问题v1到v7的最短路长及最短路线如图所示：,最短路问题,从上例知，只要某点已标号，说明已找到起点,v,s,到该点的最短路线及最短距离，因此可以将每个点标号，求出,v,s,到任意点的最短路线，如果某个点,v,j,不能标号，说明,v,s,不可达,v,j,。,注：无向图最短路的求法只将上述步骤,2,将弧改成边即可。,PPT课件,最短路问题从上例知，只要某点已标号，说明已找到起点vs到该点,最短路问题,例,6.6,求下图,v,1,到各点的最短距离及最短路线。,4,5,2,6,1,7,8,3,9,3,2,6,12,16,18,0,4,5,2,2,3,10,3,9,6,12,6,4,11,6,6,18,8,12,24,8,24,18,PPT课件,最短路问题例6.6 求下图v1到各点的最短距离及最短路线。,最短路问题,v,1,到各点的最短距离及最短路线如图所示：,4,5,2,6,1,7,8,3,9,3,2,6,12,16,18,0,2,6,18,所有点都已标号，点上的标号就是,v,1,到该点的最短距离，最短路线就是红色的链。,PPT课件,最短路问题v1到各点的最短距离及最短路线如图所示：,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,例,6.7,求从,1,到,8,的最短路径,最短路问题,PPT课件,237184566134105275934682例6.7,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X,=1,w,1,=0,min c,12,c,14,c,16,=min 0+2,0+1,0+3=min 2,1,3=1,X=1,4,p,4,=1,p,4,=1,p,1,=0,最短路问题,PPT课件,237184566134105275934682X=1,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X,=1,4,min c,12,c,16,c,42,c,47,=min 0+2,0+3,1+10,1+2=min 2,3,11,3=2,X=1,2,4,p,2,=2,p,1,=0,p,4,=1,p,2,=2,最短路问题,PPT课件,237184566134105275934682X=1,4,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X,=1,2,4,min c,1,6,c,23,c,25,c,47,=min 0+3,2+6,2+5,1+2=min 3,8,7,3=3,X=1,2,4,6,p,6,=3,p,2,=2,p,4,=1,p,1,=0,p,6,=3,最短路问题,PPT课件,237184566134105275934682X=1,2,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X,=1,2,4,6,min c,23,c,25,c,47,c,67,=min 2+6,2+5,1+2,3+4=min 8,7,3,7=3,X=1,2,4,6,7,p,7,=3,p,2,=2,p,4,=1,p,1,=0,p,6,=3,p,7,=3,最短路问题,PPT课件,237184566134105275934682X=1,2,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X,=1,2,4,6,7,min c,23,c,25,c,75,c,78,=min 2+6,2+5,3+3,3+8=min 8,7,6,11=6,X=1,2,4,5,6,7,p,5,=6,p,2,=2,p,4,=1,p,1,=0,p,6,=3,p,7,=3,p,5,=6,最短路问题,PPT课件,237184566134105275934682X=1,2,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X,=1,2,4,6,7,min c,23,c,53,c,58,c,78,=min 2+6,6+9,6+4,3+8=min 8,15,10,11=8,X=1,2,3,4,5,6,7,p,3,=8,p,2,=2,p,4,=1,p,1,=0,p,6,=3,p,7,=3,p,5,=6,p,3,=8,最短路问题,PPT课件,237184566134105275934682X=1,2,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X,=1,2,3,4,6,7,min c,38,c,58,c,78,=min 8+6,6+4,3+7=min 14,10,11=10,X=1,2,3,4,5,6,7,8,p,8,=10,p,2,=2,p,4,=1,p,1,=0,p,6,=3,p,7,=3,p,5,=6,p,3,=8,p,8,=10,最短路问题,PPT课件,237184566134105275934682X=1,2,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X,=1,2,3,4,6,7,8,1,到,8,的最短路径为,1,，,4,，,7,，,5,，,8,，长度为,10,。,p,2,=2,p,4,=1,p,1,=0,p,6,=3,p,7,=3,p,5,=6,p,3,=8,p,8,=10,最短路问题,PPT课件,237184566134105275934682X=1,2,最短路问题,课堂练习：,1.,用,Dijkstra,算法求下图从,v,1,到,v,6,的最短距离及路线。,v,3,v,5,4,v,1,v,2,v,4,v,6,3,5,2,2,2,4,2,1,v,1,到,v,6,的最短路为：,PPT课件,最短路问题课堂练习：v3v54v1v2v4v63522242,最短路问题,2.,求下图中,v,1,点到另外任意一点的最短路径,v,1,v,2,v,3,v,4,v,6,v,5,3,2,2,7,6,2,1,3,3,PPT课件,最短路问题2.求下图中v1点到另外任意一点的最短路径v1v,最短路问题,v,1,V,2,V,3,V,4,V,6,V,5,3,2,2,7,6,2,1,3,3,0,2,4,7,1,4,PPT课件,最短路问题v1V2V3V4 V6V5322762133024,最短路问题,v,1,V,2,V,3,V,4,V,6,V,5,3,2,2,7,6,2,1,3,3,0,2,4,7,1,4,PPT课件,最短路问题v1V2V3V4 V6V5322762133024,最短路问题,算法适用条件：,Dijkstra,算法只适用于全部权为非负情况，如果某边上权为负的，算法失效。此时可采用逐次逼近算法。,例,6.7,如右图所示中按,dijkstra,算法可得,P(v,1,)=5,为从,v,s,v,1,的最短路长显然是错误的，从,v,s,v,2,v,1,路长只有,3,。,v,2,v,s,v,1,5,-5,8,PPT课件,最短路问题算法适用条件：例6.7 如右图所示中按dijks,最短路问题,例,6.8,设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。已知：,设备每年年初的价格表,PPT课件,最短路问题例6.8 设备更新问题。某公司使用一台设备，在每,最短路问题,设备维修费如下表,解：将问题转化为最短路问题，如下图：用,v,i,表示,“,第,i,年年初购进一台新设备,”,弧（,v,i,v,j,）表示第,i,年年初购进的设备一直使用到第,j,年年初。,v,1,v,2,v,3,v,4,v,5,v,6,PPT课件,最短路问题设备维修费如下表解：将问题转化为最短路问题，如下图,最短路问题,把所有弧的权数计算如下表，,把权数赋到图中，再用,Dijkstra,算法求最短路。,v,1,v,2,v,3,v,4,v,5,v,6,16,22,30,41,59,16,22,30,41,31,23,17,18,17,23,W,12,=11+5=16,W,13,=11+5+6=22,W,14,=11+5+6+8=30,W,15,=11+5+6+8+11=41,W,16,=11+5+6+8+11+18=59,W,23,=11+5=16,W,24,=11+5+6=22,W,25,=11+5+6+8=30,W,26,=11+5+6+8+11=41,W,34,=12+5=17,W,35,=12+5+6=23,W,36,=12+5+6+8=31,W,45,=12+5=17,W,46,=12+5+6=23,W,56,=13+5=18,PPT课件,最短路问题把所有弧的权数计算如下表，把权数赋到图中，再用Di,最短路问题,最终得到下图，可知，,v,1,到,v,6,的距离是,53,，最短路径有两条：,v,1,v,3,v,6,和,v,1,v,4,v,6,V,1,（,0,s,）,v,3,v,4,(41,1),v,5,v,6,22,30,41,59,16,(22,1),30,41,31,23,17,18,17,23,V,2,（,16,1,）,16,(30,1),(53,3),(53,4),PPT课件,最短路问题 最终得到下图，可知，v1到v6的距离是53，最短,