最短路算法上课课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《最短路算法上课课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 短路 算法 上课 课件
- 资源描述:
-
1、A1 最短路问题及相关算法介绍吕长虹吕长虹华东师范大学数学系华东师范大学数学系Email:A2vQuestion one:v每天开车去上班,应该走那条使得达到公司的费用最每天开车去上班,应该走那条使得达到公司的费用最低、时间最少呢,如何选择最优的路径呢?低、时间最少呢,如何选择最优的路径呢?A3vQuestion two:v在城市规划自己电网架设中,怎么设计才能使其耗费在城市规划自己电网架设中,怎么设计才能使其耗费的资金最少?的资金最少?A4v 其实都涉及到一个相同的问题:最短路问题!其实都涉及到一个相同的问题:最短路问题!A5v最短路问路径不仅仅是一般地理意义上的距离最短,还可以最短路问路径
2、不仅仅是一般地理意义上的距离最短,还可以延伸到其他度量,如时间、费用、线路容量等,相应的最短延伸到其他度量,如时间、费用、线路容量等,相应的最短路问题就转化诶最快路径问题、最低费用问题。路问题就转化诶最快路径问题、最低费用问题。v最短路径问题也是资源分配,线路设计及分析等优化问题的最短路径问题也是资源分配,线路设计及分析等优化问题的基础。基础。A6 图论中的最短路问题图论中的最短路问题(shortest route problem)(shortest route problem)是组合是组合数学和图论中核心问题之一,是许多更深层次算法的数学和图论中核心问题之一,是许多更深层次算法的基础。基础。
3、A7v图的定义:图的定义:v图是一种由图是一种由“顶点顶点”组成的抽象网络,网络中的各顶点可以组成的抽象网络,网络中的各顶点可以通过通过“边边”实现彼此的连接,表示两顶点有关联。实现彼此的连接,表示两顶点有关联。图一般用图一般用G来表示,其顶点集为来表示,其顶点集为V,边集为,边集为E,简述为,简述为G=(V,E)。右图就是图论中一个节点的图结构,一共右图就是图论中一个节点的图结构,一共有有10个顶点,个顶点,15条边。条边。Petersen图A8v最短路问题就是在指定的网络中两个节点间寻找一条距离最最短路问题就是在指定的网络中两个节点间寻找一条距离最小的路。小的路。v网络就是用节点和边联结构
4、成的网络就是用节点和边联结构成的图图,如铁路网、公路网等。,如铁路网、公路网等。下图就是我们将一个实际区域结构,图结构化的结果。下图就是我们将一个实际区域结构,图结构化的结果。A9v两种常见最短路问题:两种常见最短路问题:v1、单源最短路问题:求某一个到其余个点的最短路问题?、单源最短路问题:求某一个到其余个点的最短路问题?v-dijkstra算法算法v2、多源最短路问题:求任意两点之间最短路问题?、多源最短路问题:求任意两点之间最短路问题?v-Floyd算法算法A10vDijkstra算法更是被称为统治世界的十大算法之一。算法更是被称为统治世界的十大算法之一。A11v最短路算法一个经典应用:
5、导航最短路算法一个经典应用:导航v我们在百度地图上寻找驾车路径时,显然就是要寻找一条物我们在百度地图上寻找驾车路径时,显然就是要寻找一条物理距离最短或者行驶时间最短的路线。理距离最短或者行驶时间最短的路线。v那我们能否通过算法设计一个属于我们的导航呢?那我们能否通过算法设计一个属于我们的导航呢?vDijkstra算法就可以帮助我们做到这一点!算法就可以帮助我们做到这一点!A12问题简述问题简述 现有在无向图现有在无向图 G=(V,E),V为各顶点的集合,为各顶点的集合,E边集合,边集合,W为每条路径的权值,满足为每条路径的权值,满足权值大于零。需要求得从某权值大于零。需要求得从某个起始点个起始
6、点v,到其余各点的最到其余各点的最短路径。短路径。A13Dijkstra算法算法算法描述算法描述A14Dijkstra算法描述把图中顶点集合V分成两组 第一组为已求出最短路径的顶点集合已求出最短路径的顶点集合(用S表示,初始时S中只有一个源点,以后每求得一条到其余顶点的最短路径,就将加入到集合S中,直到全部顶点都加入到S中,算法就结束了)第二组为其余未确定最短路径的顶点集合未确定最短路径的顶点集合(用U表示),按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中,总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外,每个顶点对应一个距离,每个顶
7、点对应一个距离,S中的顶点的距离中的顶点的距离就是从就是从v到此顶点的最短路径长度,到此顶点的最短路径长度,U中的顶点的距中的顶点的距离,是从离,是从v到此顶点只包括到此顶点只包括S中的顶点为中间顶点的中的顶点为中间顶点的当前最短路径长度。当前最短路径长度。A15Dijkstra算法算法步骤步骤从U中选取一个距离v最小的顶点k,把k,加入S中(该选定的距离就是v到k的最短路径长度)。二二重复步骤二和三直到所有顶点都包含在S中。四四以k为新考虑的中间点,修改U中各顶点的距离;若从源点v到顶点u的距离(经过顶点k)比原来距离(不经过顶点k)短,则修改顶点u的距离值,修改后的距离值的顶点k的距离加上
8、边上的权。三三初始时,S只包含源点,即Sv,v的距离为0。U包含除v外的其他顶点,即:U=其余顶点,若v与U中顶点u有边,则正常有权值,若u不是v的出边邻接点,则权值为。一一A16v算法的描述上看去相当复杂,我们给出下面例子来具体说明整个算法的运行流程!A17v首先我们要有如下概念:v假设P:vkm是从顶点v到km的一条最短路径,那对这条路径上任意其他一点ki,都有 P上关于v ki的子路径为v到点ki的最短路径。v即最短路径的子路径仍然是最短路径,最短路算法本质上上基于这种思想展开的。A18经典例子经典例子A19 我们取源点为V1,即求V1到其余个点的最短距离。A20STEP1:开始阶段S=
9、V1,U=V2,V3,V4,V5,V6,W=(wij)66 为权值矩阵。向量D来记录每一步之后V1与其余各点之间的最短距离。初始阶段D=(0,7,9,14)。A21STEP2:将与V1距离最小的点V2放入S中,S=V1,V2,U=V3,V4,V5,V6,此时我们确定V1到V2之间的最短距离为7。计算V1与U中各点距离【必须最短路经过V2】,再与向量D中比较取较小值作为新的D中取值。S13=W23+D12=10+7=17S14=W24+D12=15+7=22D13=minS13,D13=min17,9=9,不变。D14=minS14,D14=min22,=22,变小。此时 D=(0,7,9,22
10、,14)A22STEP3:将与V1距离最小的点V3放入S中,S=V1,V2,V3,U=V4,V5,V6,此时我们确定V1到V3之间的最短距离为9。计算V1与U中各点距离【必须最短路经过V3】,再与向量D中比较取较小值作为新的D中取值。S14=W34+D13=11+9=20S16=W36+D13=2+9=11D14=minS14,D14=min20,22=20,变小。D16=minS16,D16=min11,14=11,变小。此时 D=(0,7,9,20,11)A23STEP4:将U中与V1距离最小的点V6放入S中,S=V1,V2,V3,V6,U=V4,V5,此时我们确定V1到V6之间的最短距离
11、为11。计算V1与U中各点距离【必须最短路经过V6】,再与向量D中比较取较小值作为新的D中取值。S15=W65+D1=11+9=20D15=minS15,D15=min20,=20,变小。此时 D=(0,7,9,20,20,11)A24STEP5:此时U中与V1距离最小的点为V4和V5放入S中,S=V1,V2,V3,V4,V5,V6,U=,此时我们确定V1到V4之间的最短距离为20,V1到V5之间的最短距离也为20。所有的点都在S中,算法终止!此时 D=(0,7,9,20,20,11),就是V1到其余各个点的最短距离向量。A25 优点优点缺点缺点优点优点优点优点缺点缺点缺点效率低,需要遍历所有
12、点(特别是有时候不需要最优解)、运算中占用空间大缺点缺点算法简明易懂、并且一定能得到最优解优点优点Dijkstra算法可能不是最优先使用的方法,因为算法的运算速度效率,往往要比精确度更加重要实际运用实际运用A26这样利用这样利用Dijkstra算法设计一个属于我们自己的导航系统啦。算法设计一个属于我们自己的导航系统啦。但似乎在实际运行时效果并不理想!但似乎在实际运行时效果并不理想!A27v虽然算法本身就是最短路径,但路面交通变化复杂,由于路虽然算法本身就是最短路径,但路面交通变化复杂,由于路面施工导致道路封锁,同时还存在路堵、车祸等现象,导致面施工导致道路封锁,同时还存在路堵、车祸等现象,导致
13、算法输出的最优路径,实际上并不是我们想要的最优路径。算法输出的最优路径,实际上并不是我们想要的最优路径。A28路面道路封锁、路堵、车祸等现象,本质上可以理解为这条道路面道路封锁、路堵、车祸等现象,本质上可以理解为这条道路被封堵住了,即有一个障碍物出现在此处,阻碍我们继续前路被封堵住了,即有一个障碍物出现在此处,阻碍我们继续前进了!进了!A29v这时候我们这时候我们Dijkstra算法就失效了!算法就失效了!v有同学会问:去掉这条堵住的线段不就可以了?这样仍然可有同学会问:去掉这条堵住的线段不就可以了?这样仍然可以用以用Dijkstra算法求解。算法求解。v事实上这是一种可行的思路,但如果这样操
展开阅读全文