教案_图论31.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《教案_图论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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 教案 图论 31
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内