最短路问题Dijkstra-Floyd-算法课件.ppt

最短路问题Dijkstra-Floyd-算法课件.ppt

ID:57201787

大小:1.13 MB

页数:58页

时间:2020-08-03

最短路问题Dijkstra-Floyd-算法课件.ppt_第1页
最短路问题Dijkstra-Floyd-算法课件.ppt_第2页
最短路问题Dijkstra-Floyd-算法课件.ppt_第3页
最短路问题Dijkstra-Floyd-算法课件.ppt_第4页
最短路问题Dijkstra-Floyd-算法课件.ppt_第5页
资源描述:

《最短路问题Dijkstra-Floyd-算法课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、最短路问题最短路问题Dijkstra算法Ford算法Floyd算法一、最短路问题例下图为单行线交通网,每弧旁的数字表示通过这条线所需的费用。现在某人要从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的旅行路线从v1到v8的路。旅行路线总费用路上所有弧权之

2、和。最短路问题中,不考虑有向环、并行弧。v2v523464v3v1v4v6121061210v8v9v72363最短路问题给定有向网络D=(V,A,W),任意弧aij∈A,有权w(aij)=wij,给定D中的两个顶点vs,vt。设P是D中从vs到vt的一条路,定义路P的权(长度)是P中所有弧的权之和,记为w(P)。最短路问题就是要在所有从vs到vt的路中,求一条路P0,使称P0是从vs到vt的最短路。路P0的权称为从vs到vt的路长。记为ust。二、Dijkstra算法当所有wij≥0时,本算法是

3、用来求给定点vs到任一个点vj最短路的公认的最好方法。事实:如果P是D中从vs到vj的最短路,vi是P中的一个点,那么,从vs沿P到vi的路是从vs到vi的最短路。最短路的子路也是最短路。思想:将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,v

4、2),…,Pk=P(vs,vk)P1一定只有一条弧。记则使上式达到最小值的点v’可取为vk+1。计算过程中可采用标号方法。Xk中的点,ui值是vs到vi的最短路长度,相应的点记“永久”标号;XK中的点,ui值是vs到vi的最短路长度的上界,相应的点记“临时”标号,供进一步计算使用。前点标号i:表示点vs到vj的最短路上vj的前一点。如i=m,表示vs到vj的最短路上vj前一点是vm。1,6图上标号法:v5v223464v3v1v4121061210v8v9v72363v60,01,∞1,∞1,

5、11,∞1,∞1,∞1,31,6图上标号法:v5v223464v3v1v4121061210v8v9v72363v60,01,∞1,∞1,11,∞1,∞1,∞1,31,6v5v223464v3v1v4121061210v8v9v72363v60,01,∞4,111,11,∞1,∞1,∞1,3图上标号法:1,5v5v223464v3v1v4121061210v8v9v72363v60,01,∞4,111,11,∞1,∞1,∞1,31,6图上标号法:1,5v5v223464v3v1v412106121

6、0v8v9v72363v60,01,∞4,111,11,∞1,∞1,∞1,33,5图上标号法:3,5v5v223464v3v1v4121061210v8v9v72363v60,01,∞4,111,11,∞1,∞1,31,∞图上标号法:3,5v5v223464v3v1v4121061210v8v9v72363v60,01,∞4,111,11,∞1,∞1,31,∞图上标号法:3,5v5v223464v3v1v4121061210v8v9v72363v60,04,111,11,∞2,61,∞1,31,∞

7、图上标号法:3,5v5v223464v3v1v4121061210v8v9v72363v60,04,111,11,∞2,61,∞1,31,∞图上标号法:3,5v5v223464v3v1v4121061210v8v9v72363v60,05,101,11,∞2,65,121,35,9图上标号法:3,5v5v223464v3v1v4121061210v8v9v72363v60,05,101,11,∞2,65,121,35,9图上标号法:Dijkstra算法步骤:第1步:令us=0,uj=wsj(1≤j

8、≤n)若asjA,则第2步:(选永久标号)在XK中选一点vi,满足第3步:(给点vi永久性标号)第4步:(修改临时标号)对所有如果令j=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≤j≤n)从vs到XK中各点没有路;否则,转第3步。如果Xk+1=,结束,到所有的点的最短路已经求得;否则,转第4步。例用Dij

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。