教案_图论31.ppt

《教案_图论31.ppt》由会员分享，可在线阅读，更多相关《教案_图论31.ppt（43页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、 第三节第三节 最短路问题最短路问题一、最短路问题一、最短路问题例例 下图为单行线交通网，每弧旁的数字表示通过这条下图为单行线交通网，每弧旁的数字表示通过这条 线所需的费用。现在某人要从线所需的费用。现在某人要从v1出发，通过这个交出发，通过这个交 通网到通网到v8去，求使总费用最小的旅行路线。去，求使总费用最小的旅行路线。v2v523464v3v1v4v6121061210v8v9v72363从从v1到到v8：P1=（v1，v2，v5，v8）费用费用 6+1+6=13P2=（v1，v3，v4，v6，v7，v8）费用费用 3+2+10+2+4=21P3=从从v1到到v8的旅行路线的旅行路线 从

2、从v1到到v8的路。的路。旅行路线总费用旅行路线总费用 路上所有弧权之和。路上所有弧权之和。最短路问题中，不考虑有向环、并行弧。最短路问题中，不考虑有向环、并行弧。v2v523464v3v1v4v6121061210v8v9v72363最短路问题最短路问题 给定有向网络给定有向网络D=（V，A，W），），任意弧任意弧aijA，有权有权w（aij）=wij，给定给定D中的两个顶点中的两个顶点vs，vt。设。设P是是D中从中从vs到到vt的一条路，定义路的一条路，定义路P的权（长度）是的权（长度）是P中所有弧的权之和，记为中所有弧的权之和，记为w（P）。）。最短路问题就是要最短路问题就是要在所有从

3、在所有从vs到到vt的路中，求一条路的路中，求一条路P0，使使 称称P0是从是从vs到到vt的最短路。路的最短路。路P0的权称为从的权称为从vs到到vt的路长。记为的路长。记为ust。二、二、Dijkstra算法算法 当所有当所有 wij 0 时，时，本算法是用来本算法是用来求给定点求给定点vs到到任一个点任一个点vj 最短路最短路的公认的最好方法。的公认的最好方法。事实：如果事实：如果P是是D中从中从vs到到vj的最短路，的最短路，vi是是P中的一中的一个点，那么，从个点，那么，从vs沿沿P到到vi的路是从的路是从vs到到 vi的最短路。的最短路。最短路的子路也是最短路。最短路的子路也是最短

4、路。思想：将思想：将D=（V，A，W）中）中vs到所有其它顶点的最短到所有其它顶点的最短 路按其路按其路长路长从小到大排列为：从小到大排列为：u0 u1 u2 unu0表示表示vs到自身的长度，相应最短路记为：到自身的长度，相应最短路记为：P0，P1，P2，Pn，取最小值的点为取最小值的点为v1，P1=P（vs，v1）假定假定 u0，u1，uk的值已求出，对应的最短路的值已求出，对应的最短路分别为分别为P1=P（vs，v1），），P2=P（vs，v2），），Pk=P（vs，vk）P1一定只有一条弧。一定只有一条弧。记记则则 使上式达到最小值的点使上式达到最小值的点v 可取为可取为vk+1。计算

5、过程中可采用标号方法。计算过程中可采用标号方法。Xk中的点，中的点，ui 值是值是vs 到到vi 的最短路长度，相应的的最短路长度，相应的点记点记“永久永久”标号；标号；XK中的点，中的点，ui值是值是vs到到vi的最短路长度的上界，的最短路长度的上界，相应的点记相应的点记“临时临时”标号，供进一步计算使用。标号，供进一步计算使用。前点标号前点标号 i:表示点表示点vs到到vj的最短路上的最短路上vj的前一点。的前一点。如如 i=m，表示表示vs到到vj的最短路上的最短路上vj前一点是前一点是vm。1,6图上标号法图上标号法:v5v223464v3v1v41210 6 1210v8v9v723

6、63v60,01,1,1,11,1,1,1,31,6图上标号法图上标号法:v5v223464v3v1v41210 6 1210v8v9v72363v60,01,1,1,11,1,1,1,31,6图上标号法图上标号法:v5v223464v3v1v41210 6 1210v8v9v72363v60,01,4,111,11,1,1,1,31,5图上标号法图上标号法:v5v223464v3v1v41210 6 1210v8v9v72363v60,01,4,111,11,1,1,1,31,61,5图上标号法图上标号法:v5v223464v3v1v41210 6 1210v8v9v72363v60,01,

7、4,111,11,1,1,1,33,53,5图上标号法图上标号法:v5v223464v3v1v41210 6 1210v8v9v72363v60,01,4,111,11,1,1,31,3,5图上标号法图上标号法:v5v223464v3v1v41210 6 1210v8v9v72363v60,01,4,111,11,1,1,31,3,5图上标号法图上标号法:v5v223464v3v1v41210 6 1210v8v9v72363v60,04,111,11,2,61,1,31,3,5图上标号法图上标号法:v5v223464v3v1v41210 6 1210v8v9v72363v60,04,111,

8、11,2,61,1,31,3,5图上标号法图上标号法:v5v223464v3v1v41210 6 1210v8v9v72363v60,05,101,11,2,65,121,35,93,5图上标号法图上标号法:v5v223464v3v1v41210 6 1210v8v9v72363v60,05,101,11,2,65,121,35,9Dijkstra算法步骤：算法步骤：第第1步：令步：令us=0，uj=wsj （1jn）若）若asj A，则则第第2步：步：(选永久标号选永久标号)在在XK中选一点中选一点vi，满足满足 第第3步：（给点步：（给点vi永久性标号）永久性标号）第第4步：步：(修改临时

9、标号修改临时标号)对所有对所有 如果如果 令令 i=i，uj=ui+wij否则否则,i,uj 不变不变,把把k换成换成k+1，返回第返回第2步。步。如果如果ui=+，停止，停止，令令Xk+1=Xk vi,Xk+1=Xk vi 令令wsj=+,X0=vs,X0=VX0,k=0,i=0(0 jn）从从vs到到XK中各点没有路；否则，转第中各点没有路；否则，转第3步。步。如果如果Xk+1=，结束，到所有的点的最短路已经求结束，到所有的点的最短路已经求得得；否则，转第；否则，转第4步。步。例例 用用Dijkstra算法求前面例子中从算法求前面例子中从v1到各点的最短路。到各点的最短路。解：解：u1=0

10、，u2=6，u3=3，u4=1，u5=u6=u7=u8=u9=+，j=1 （j=2，3，9）X0=v1，X0=v2，v3，v9v2v523464v3v1v4v6121061210v8v9v72363K=0 minu2，u3，u4，u5，u6，u7，u8，u9 =min6，3，1，=1=u4 点点v4得永久标号，得永久标号，4=1，X1=v1，v4，X1=v2，v3，v5，v6，v7，v8，v9，在所有在所有vjX1中，中，u6=，u4+w46=1+10=11，即即 u4+w46 u6 修改临时标号修改临时标号u6=11，6=4，其余标号不变。其余标号不变。v2v523464v3v1v4v612

11、1061210v8v9v72363K=0+1=1 minu2，u3，u5，u6，u7，u8，u9 =min6，3，11，=3=u3 点点v3得永久标号，得永久标号，3=1，X2=v1，v4，v3，X2=v2，v5，v6，v7，v8，v9，u2=6，u3+w32=3+2=5，即即 u3+w32 u2 修改临时标号修改临时标号u2=5，2=3，其余标号不变。其余标号不变。在所有在所有vjX2中中，k=2+1=3 minu5，u6，u7，u8，u9 =min6，11，=6=u5 点点v5得永久标号，得永久标号，5=2，X4=v1，v4，v3，v2，v5，X4=v6，v7，v8，v9，u6=11，u5

12、+w56=6+4=10，即即 u5+w56 u6 u7=，u5+w57=6+3=9，即即 u5+w57 u7 u8=，u5+w58=6+6=12，即即 u5+w58 u8 修改临时标号修改临时标号u6=10，6=5，u7=9，7=5，u8=12，8=5，在所有在所有vjX4中，中，K=3+1=4 minu6，u7，u8，u9 =min10，9，12，=9=u7 点点v7得永久标号，得永久标号，7=5，X2=v1，v4，v3，v2，v5，v7，X2=v6，v8，v9，在在vjX5中，临时标号不变。中，临时标号不变。K=4+1=5 minu6，u8，u9=min10，12，=10=u6 点点v6得

13、永久标号，得永久标号，6=5，X6=v1，v4，v3，v2，v5，v7 ，v6，X6=v8，v9，点点v8，v9临时标号不变。临时标号不变。K=5+1=6 minu8，u9=min12，=12=u8 点点v8得永久标号，得永久标号，8=5，即从即从v1到到v8的最短路长为的最短路长为u8=12，8=5，5=2，2=3，3=1，知从知从v1到到v8 的最短路为：的最短路为：P1，8=P（v1，v3，v2，v5，v8）v2v523464v3v1v4v6121061210v8v9v72363问题：问题：本例中，本例中，v1到到v9的最短路？的最短路？无向网络无向网络:负权弧时负权弧时。wijvivj

14、wijwijvjvi无向网络中，最短路无向网络中，最短路最短链最短链。多个点对之间最短路？多个点对之间最短路？v1v2v312-3Dijkstra算法失效算法失效三、三、Floyd算法算法 网络网络D=（V，A，W），令），令U=(uij)n n，表示表示D中中vi到到vj的最短路的长度。的最短路的长度。考虑考虑D中任意两点中任意两点vi，vj，如将如将D中中vi，vj以外的点以外的点都删掉，得只剩都删掉，得只剩vi，vj的一个子网络的一个子网络D0，记记wij为弧（为弧（vi，vj）的权。的权。在在D0中加入中加入v1及及D中与中与vi，vj，v1相相关联的弧，得关联的弧，得D1，D1中中v

15、i到到vj的最短路的最短路长记为长记为 ,则一定有则一定有vivjv1wij 再在再在D1中加入中加入v2及及D中与中与vi，vj，v1，v2相关联的相关联的弧，得弧，得D2，D2中中vi到到vj的最短路长记为的最短路长记为 ，则有，则有 递推，递推，D中中n个点逐个加入子网络，终得个点逐个加入子网络，终得D中中vi到到vj的最短路路长的最短路路长 如果计算结果希望给出具体的最短路的路径，如果计算结果希望给出具体的最短路的路径，则构造路径矩阵则构造路径矩阵S=(sij)n n,sij表示表示vi到到vj的最短路的最短路的第一条弧的终点的第一条弧的终点。如。如 ，则从，则从vi到到vj的最短的最

16、短路的第一条弧为（路的第一条弧为（vi，vt），），第二条弧为从第二条弧为从vt到到vj的的最短路的第一条弧。最短路的第一条弧。Floyd算法步骤：算法步骤：第第1步：步：第第2步：计算步：计算其中其中第第3步：当步：当k=n时，时，是是vi到到 vj最短路第一条弧的终点。最短路第一条弧的终点。是是vi到到 vj最短路路长。最短路路长。例例 求如下网络中各点对间最短路的路长。求如下网络中各点对间最短路的路长。v2v52-344v3v1v4-2658解：解：用用U(0)的第一行、第的第一行、第一列来修正其余的一列来修正其余的uij，即即作作min ，4+5同时，在修正同时，在修正 处修改处修改1

17、1与与v4到到v1的第的第一段弧一段弧相同相同用用U（1）的第二行、第二列修正其余的的第二行、第二列修正其余的uij，vivjv1v22211与与v1到到v2的第一的第一段弧相段弧相同同用用U(2)第三行、第三列修正其余的第三行、第三列修正其余的用用U(3)第四行、第四列修正其余的第四行、第四列修正其余的4 4 4用用U(4)第五行、第五列修正其余的第五行、第五列修正其余的25255555从从v1到到v3的最短路长度的最短路长度 。从从v5到到v2的最短路长度的最短路长度 路径路径：v1到到v3的最短路路经为的最短路路经为:P13=P(v1,v2,v5,v4,v3)路径路径：v5到到v2的最短

18、路路经为的最短路路经为:P52=P(v5,v4,v1,v2)v1v2v5v4 v3v5v3v4v2v153436-412-2U(5)=000004538316-2372-1-13-41041-1S(5)=1234523333334523542121211练习：求各点间练习：求各点间最短路径及长度最短路径及长度四、四、Ford算法算法算法思想：逐次逼近算法思想：逐次逼近每次逼近是求每次逼近是求D中从顶点中从顶点V1到其余各点的带有限制的最短路。到其余各点的带有限制的最短路。第一次：自顶点到vj由一条弧组成的路中找一条最短的第二次：自顶点到vj由不多于两条弧组成的路中找一条最短的第m次：自顶点到v

19、j由不多于m条弧组成的路中找一条最短的最多进行n-1次逼近定理：设网络D不含负回路，pj(m)是D的自顶点v1到顶点vj由不多于m条弧组成的路中长度最小者，w(pj(m)=uj(m)，j=2,3,n,则对于一切2 j n,有uj(1)uj(m)=w1jminuj(m)+wkj1 k n2 m n-1算法步骤：算法步骤：令 l(v1)=0,l(uj)=1(2 j n);m=1,u1(m)=0，uj(m)=w1j (2 j n)。步骤0步骤2 若m+1=n-1，结束。若m+1n-1，置m=m+1，转步骤，转步骤1 步骤1 对于一切2 j n，计算minuk(m)+wkj1 k n。设minuj(m

20、)+wkj1 k n=ur(m)+wrj令uj(m+1)=ur(m)+wrj及l(vj)=l(vj)r若r=j其它v1v4v5v3v22251-433例例1练习练习v1v4v5v3v21-2-33-221v621-2例例 2 某台机器可连续工作某台机器可连续工作4年，也可于每年末卖掉，年，也可于每年末卖掉，换一台新的。已知于各年初购置一台新机器的价格及换一台新的。已知于各年初购置一台新机器的价格及不同役龄机器年末的处理价格如下表。新机器第一年不同役龄机器年末的处理价格如下表。新机器第一年运行及维修费为运行及维修费为0.3万元，使用万元，使用1-3年后机器每年的运年后机器每年的运行及维修费用分别

21、为行及维修费用分别为0.8，1.5，2.0万元。试确定该机万元。试确定该机器的最优更新策略，使器的最优更新策略，使4年内用于更换、购买及运行年内用于更换、购买及运行维修的总费用为最省。维修的总费用为最省。j第一年第一年 第二年第二年 第三年第三年 第四年第四年年初购置价年初购置价使用使用j年的机器处理价年的机器处理价2.52.02.61.62.81.33.11.1解题思路解题思路：设：设v1v2v3v4v5为各年年初，为各年年初，vij(ij)为从为从i年使用到年使用到j年年例例 3 某公司在六个城市某公司在六个城市c1,c6中有分公司，从中有分公司，从ci到到cj的直接航程票价记在下述矩阵中

22、的的直接航程票价记在下述矩阵中的(i,j)位置上。位置上。（表示无直接航路），请帮助该公司设计一张任意两城表示无直接航路），请帮助该公司设计一张任意两城市间的票价最便宜的路线表。市间的票价最便宜的路线表。0 50 40 25 10500 15 20 25 15 0 10 20 25 20 10 0 5510 25 25 55 0例例 4 已知有已知有6个村子，相互间道路的距离如下图示。个村子，相互间道路的距离如下图示。拟合建一所小学，已知拟合建一所小学，已知A处有小学生处有小学生50人，人，B处处40人，人，C处处60人，人，D处处20人，人，E处处70人，人，F处处90人，问小学人，问小学应建在哪一个村子，使学生上学最方便（原则应建在哪一个村子，使学生上学最方便（原则所所有人走的总路程最短；有人走的总路程最短；尽可能公平。）。尽可能公平。）。AFEDCB2781361364解题思路解题思路：先求出各点之间的最短路路长：先求出各点之间的最短路路长6种设置方法种设置方法中总走行最短的中总走行最短的 6种种设置方法最设置方法最长与最短的差最长与最短的差最小的。小的。