算法合集之《最短路算法及其应用》.ppt
《算法合集之《最短路算法及其应用》.ppt》由会员分享,可在线阅读,更多相关《算法合集之《最短路算法及其应用》.ppt(30页珍藏版)》请在三一办公上搜索。
1、最短路算法及其应用,广东北江中学 余远铭,最短路问题是图论中的核心问题之一,它是许多更深层算法的基础。同时,该问题有着大量的生产实际的背景。不少问题从表面上看与最短路问题没有什么关系,却也可以归结为最短路问题。,乘汽车旅行的人总希望找出到目的地尽可能短的行程。如果有一张地图并在地图上标出了每对十字路口之间的距离,如何找出这一最短行程?,一个在生活中常见的例子是:,一种可能的方法是枚举出所有路径,并计算出每条路径的长度,然后选择最短的一条。,然而我们很容易看到,即使不考虑含回路的路径,依然存在数以百万计的行车路线!,实际上,其中绝大多数路线我们是没必要考虑的。,这时候,我们应该用一种系统的方法来
2、解决问题,而不是通常人们所用的凑的方法和凭经验的方法。,定义,在最短路问题中,给出的是一有向加权图G=(V,E),在其上定义的加权函数W:ER为从边到实型权值的映射。路径P=(v0,v1,vk)的权是指其组成边的所有权值之和:,定义u到v间最短路径的权为:,从结点u到结点v的最短路径定义为权 的任何路径。,在乘车旅行的例子中,我们可以把公路地图模型化为一个图:结点表示路口,边表示连接两个路口的公路,边权表示公路的长度。我们的目标是从起点出发找一条到达目的地的最短路径。,边的权常被解释为一种度量方法,而不仅仅是距离。它们常常被用来表示时间、金钱、罚款、损失或任何其他沿路径线性积累的数量形式。,重
3、要性质,定理1(最优子结构)给定有向加权图G=(V,E),设P=为从结点v1到结点vk的一条最短路径,对任意i,j有i为从vi到vj的P的子路径,则Pij是从vi到vj的一条最短路径。,证明:我们把路径P分解为。则w(P)=w(P1i)+w(Pij)+w(Pjk)。现在假设从vi到vj存在一路径Pij,且w(Pij)w(Pij),则将P中的路径Pij=(vi,vi+1,vj)替换成Pij,依然是从v1到vk的一条路径,且其权值 w(P1i)+w(Pij)+w(Pjk)小于w(P),这与前提P是从v1到vk的最短路径矛盾。(证毕),推论,推论1.1 给定有向加权图G=(V,E),源点为s,则对于
4、所有边(u,v)E,有:,证明:从源点s到结点v的最短路径P的权不大于从s到v的其它路径的权。特别地,路径P的权也不大于某特定路径的权,该特定路径为从s到u的最短路径加上边(u,v)。(证毕),松弛技术,INITIALIZE-SINGLE-SOURCE(G,s)1.For 每个结点 v VG2.Do dv 3.v NIL4.ds 0,对每个结点v V,我们设置一属性dv来描述从源s到v的最短路径的权的上界,称之为最短路径估计。我们通过下面的过程对最短路径估计和先辈初始化。,RELAX(u,v,w)1.If dv du+w(u,v)2.Then dv du+w(u,v)3.v u,一次松弛操作可
5、以减小最短路径的估计值dv并更新v的先辈域 v,常用算法,一、Dijkstra算法,二、Bellman-Ford算法,三、SPFA算法,Dijkstra算法,Dijkstra算法中设置了一结点集合S,从源结点s到集合S中结点的最终最短路径的权均已确定,即对所有结点v S,有dv=(s,v)。算法反复挑选出其最短路径估计为最小的结点u V-S,把u插入集合S中,并对离开u的所有边进行松弛。,Dijkstra(G,w,s)1.INITIALIZE-SINGLE-SOURCE(G,S)2.S3.Q VG4.While Q5.Do u EXTRACT-MIN(Q)6.S S U u7.For 每个顶点
6、v Adju8.Do RELAX(u,v,w),Dijkstra算法,适用条件:所有边的权值非负,定理2 每当结点u插入集合S时,有du=(s,u)成立。,简证:我们每次选择在集合V-S中具有最小最短路径估计的结点u,因为我们约定所有的边权值非负,所以有可能对结点u进行松弛操作的结点必不在集合V-S中(否则与结点u的定义矛盾),因此只会在集合S中。又由于我们选取结点进入S时,S中的结点已全部进行过松弛操作了,所以du的值不会再发生改变。因此du=(s,u)。(证毕),效率:,用一维数组来实现优先队列Q,O(),适用于中等规模的稠密图,二叉堆来实现优先队列Q,O(E+V)logV),适用于稀疏图
7、,用Fibonacci堆来实现优先队列Q的话,O(VlogV),可惜编程复杂度过高,理论价值远大于实用价值,Bellman-Ford算法,Bellman-Ford算法运用了松弛技术,对每一结点v V,逐步减小从源s到v的最短路径的估计值dv直至其达到实际最短路径的权(s,v),如果图中存在负权回路,算法将会报告最短路不存在。,Bellman-Ford(G,w,s)1.INITIALIZE-SINGLE-SOURCE(G,s)2.For i 1 to|VG|-13.Do For 每条边(u,v)EG4.Do RELAX(u,v,w)5.For 每条边(u,v)EG6.Do If dv du+w(
8、u,v)7.Then Return FALSE8.Return TRUE,Bellman-Ford算法,适用条件:任意边权为实数的图,Bellman-Ford算法的思想基于以下事实:“两点间如果有最短路,那么每个结点最多经过一次。也就是说,这条路不超过n-1条边。”(如果一个结点经过了两次,那么我们走了一个圈。如果这个圈的权为正,显然不划算;如果是负圈,那么最短路不存在;如果是零圈,去掉不影响最优值),根据最短路的最优子结构(定理1),路径边数上限为k时的最短路可以由边数上限为k-1时的最短路“加一条边”来求,而根据刚才的结论,最多只需要迭代n-1次就可以求出最短路。,效率:,Bellman-
9、Ford算法的运行时间为O(VE)。很多时候,我们的算法并不需要运行|V|-1次就能得到最优值。对于一次完整的第3-4行操作,要是一个结点的最短路径估计值也没能更新,就可以退出了。,经过优化后,对于多数情况而言,程序的实际运行效率将远离O(VE)而变为O(kE),其中k是一个比|V|小很多的数。,SPFA算法,设立一个先进先出的队列用来保存待优化的结点,优化时每次取出队首结点u,并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作,如果v点的最短路径估计值有所调整,且v点不在当前的队列中,就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作,直至队列空为止。,SPFA(G,w
10、,s)1.INITIALIZE-SINGLE-SOURCE(G,s)2.INITIALIZE-QUEUE(Q)3.ENQUEUE(Q,s)4.While Not EMPTY(Q)5.Do u DLQUEUE(Q)6.For 每条边(u,v)EG7.Do tmp dv8.Relax(u,v,w)9.If(dv tmp)and(v不在Q中)10.ENQUEUE(Q,v),我们用数组d记录每个结点的最短路径估计值,而且用邻接表来存储图G。我们采取的方法是动态逼近法:,SPFA算法,适用条件:任意边权为实数的图,定理3 只要最短路径存在,上述SPFA算法必定能求出最小值。,证明:每次将点放入队尾,都是
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 最短路算法及其应用 算法 短路 及其 应用

链接地址:https://www.31ppt.com/p-6596885.html