算法合集之《最短路算法及其应用》.ppt

最短路算法及其应用,广东北江中学 余远铭,最短路问题是图论中的核心问题之一，它是许多更深层算法的基础。同时，该问题有着大量的生产实际的背景。不少问题从表面上看与最短路问题没有什么关系，却也可以归结为最短路问题。,乘汽车旅行的人总希望找出到目的地尽可能短的行程。如果有一张地图并在地图上标出了每对十字路口之间的距离，如何找出这一最短行程？,一个在生活中常见的例子是:,一种可能的方法是枚举出所有路径，并计算出每条路径的长度，然后选择最短的一条。,然而我们很容易看到，即使不考虑含回路的路径，依然存在数以百万计的行车路线!,实际上，其中绝大多数路线我们是没必要考虑的。,这时候，我们应该用一种系统的方法来解决问题，而不是通常人们所用的凑的方法和凭经验的方法。,定义,在最短路问题中，给出的是一有向加权图G=(V,E)，在其上定义的加权函数W:ER为从边到实型权值的映射。路径P=(v0,v1,vk)的权是指其组成边的所有权值之和：,定义u到v间最短路径的权为：,从结点u到结点v的最短路径定义为权 的任何路径。,在乘车旅行的例子中，我们可以把公路地图模型化为一个图：结点表示路口，边表示连接两个路口的公路，边权表示公路的长度。我们的目标是从起点出发找一条到达目的地的最短路径。,边的权常被解释为一种度量方法，而不仅仅是距离。它们常常被用来表示时间、金钱、罚款、损失或任何其他沿路径线性积累的数量形式。,重要性质,定理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，则对于所有边(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,一次松弛操作可以减小最短路径的估计值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 每个顶点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)，适用于稀疏图,用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(u,v)7.Then Return FALSE8.Return TRUE,Bellman-Ford算法,适用条件:任意边权为实数的图,Bellman-Ford算法的思想基于以下事实：“两点间如果有最短路，那么每个结点最多经过一次。也就是说，这条路不超过n-1条边。”（如果一个结点经过了两次，那么我们走了一个圈。如果这个圈的权为正，显然不划算；如果是负圈，那么最短路不存在；如果是零圈，去掉不影响最优值）,根据最短路的最优子结构（定理1），路径边数上限为k时的最短路可以由边数上限为k-1时的最短路“加一条边”来求，而根据刚才的结论，最多只需要迭代n-1次就可以求出最短路。,效率:,Bellman-Ford算法的运行时间为O(VE)。很多时候，我们的算法并不需要运行|V|-1次就能得到最优值。对于一次完整的第3-4行操作，要是一个结点的最短路径估计值也没能更新，就可以退出了。,经过优化后，对于多数情况而言，程序的实际运行效率将远离O(VE)而变为O(kE)，其中k是一个比|V|小很多的数。,SPFA算法,设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。,SPFA(G,w,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算法必定能求出最小值。,证明：每次将点放入队尾，都是经过松弛操作达到的。换言之，每次的优化将会有某个点v的最短路径估计值dv变小。所以算法的执行会使d越来越小。由于我们假定图中不存在负权回路，所以每个结点都有最短路径值。因此，算法不会无限执行下去，随着d值的逐渐变小，直到到达最短路径值时，算法结束，这时的最短路径估计值就是对应结点的最短路径值。（证毕）,定理4 在平均情况下，SPFA算法的期望时间复杂度为O(E)。,证明：上述算法每次取出队首结点u，并访问u的所有临结点的复杂度为O(d)，其中d为点u的出度。运用均摊分析的思想，对于|V|个点|E|条边的图，点的平均出度为，所以每处理一个点的复杂度为O()。假设结点入队次数为h，显然h随图的不同而不同。但它仅与边权值分布有关。我们设h=kV，则算法SPFA的时间复杂度为 在平均的情况下，可以将k看成一个比较小的常数，所以SPFA算法在一般情况下的时间复杂度为O(E)。（证毕）,小结,Dijkstra算法的效率高，但是也有局限性，就是对于含负权的图无能为力。,Bellman-Ford算法对于所有最短路长存在的图都适用，但是效率常常不尽人意。,SPFA算法可以说是综合了上述两者的优点。它的效率同样很不错，而且对于最短路长存在的图都适用，无论是否存在负权。它的编程复杂度也很低，是高性价比的算法。,我们应该根据实际需要，找到时空复杂度和编程复杂度的平衡点，在考场上用最少的时间拿尽可能多的分数。,例一 双调路径(BOI2002),如今的道路密度越来越大，收费也越来越多，因此选择最佳路径是很现实的问题。城市的道路是双向的，每条道路有固定的旅行时间以及需要支付的费用。路径由连续的道路组成。总时间是各条道路旅行时间的和，总费用是各条道路所支付费用的总和。同样的出发地和目的地，如果路径A比路径B所需时间少且费用低，那么我们说路径A比路径B好。对于某条路径，如果没有其他路径比它好，那么该路径被称为最优双调路径。这样的路径可能不止一条，或者说根本不存在。给出城市交通网的描述信息，起始点和终点城市，求最优双条路径的条数。城市不超过100个，边数不超过300，每条边上的费用和时间都不超过100。,题意简述：,例一 双调路径(BOI2002),这道题棘手的地方在于标号已经不是一维，而是二维，因此不再有全序关系。我们可以采用拆点法，让di,c表示从s到i费用为c时的最短时间。,分析：,算法一：标号设定算法是根据拓扑顺序不断把临时标号变为永久标号的。在这题中，其实，我们并不需要严格的拓扑顺序，而只需要一个让标号永久化的理由。拓扑顺序能保证标号的永久化，但是还有其他方式。在本题中，标号永久化的条件是：从其他永久标号得不到费用不大于c且时间不大于t的临时标号（这里利用了费用和时间的非负性），即：所有的“极小临时标号”都可以永久化。这样，一个附加的好处是一次把多个临时标号同时变成永久的。,例一 双调路径(BOI2002),假设时间上限为t，费用上限为c，城市数为n，边数为m，则每个点上的标号不超过O(nc)个，标号总数为O(n*n*c)个，每条边考虑O(nc)次。如果不同顶点在同一费用的临时标号用堆来维护，不同费用的堆又组成一个堆的话，那么建立（或更新）临时标号的时间为O(mnclognlogc)，总的时间复杂度为O(nnc+mnclognlogc)，本题的规模是完全可以承受的。实际上由于标号的次数往往远小于nnc，程序效率是相当理想的,算法二：在本题中构图直接用SPFA算法。在最坏情况下，费用最大值c为100*100=10000，那么每个点将被拆成10000个点，由于原图边数不超过300，所以我们构造的新图中边数不会超过3000000。因此算法的时间复杂度是O(k*3000000)。写出来的程序运行的实际效果非常好，每个数据的速度都比官方参考程序（算法一）快，有几个甚至比官方程序快34倍！完全通过这题简直是轻而易举。这和我们对时间复杂度在理论上的分析是一致的。,例一 双调路径(BOI2002),两个算法在空间上是同阶的，一样是O(E)。虽然算法一仅用到二叉堆，并不是特别复杂，但是因为要用两个堆，建立更新删除写起来还是有一定的工作量的。SPFA算法写起来极其简单，效率又高，而且适用范围广（可以处理含有负权的图），在很多情况下，是最短路问题上好的选择。,例二 网络提速(经典问题),某学校的校园网由n(1=n=50)台计算机组成，计算机之间由网线相连，其中顶点代表计算机，边代表网线。不同网线的传输能力不尽相同。现学校购买了m(1=m=10)台加速设备，每台设备可作用于一条网线，使网线上传输信息用时减半。多台设备可用于同一条网线，其效果叠加。如何合理使用这些设备，使计算机1到计算机n传输用时最少，这个问题急需解决。校方请你编程解决这个问题。,题意简述：,例二 网络提速(经典问题),如图，若n=5，m=2，则将两台设备分别用于1-3，3-5的线路，传输用时可减少为22秒，这是最佳解。,例二 网络提速(经典问题),让我们重新描述一下问题：给定含有n个顶点的带权无向图，一共可以进行m次操作，每次操作将一条边的权值除以2。问每次应该对哪条边进行操作，使得1到n的最短路径权和最小。,分析：,如果我们把Dijkstra算法直接用在原图上，得到的是没有使用任何加速设备顶点1到顶点n的最短路长，不是我们想要的结果。,经过简单的举例后发现行不通。,能否用增量法做这题呢？就是，我们先求出使用前m-1台加速设备的最短路长，然后通过枚举之类算出第m台设备用在那条边上，行不行呢？,例二 网络提速(经典问题),一个明显的反例是：,如果我们只有一个加速设备的话，显然将它加在1-2上，那么最短路长16是最佳的。,但是，我们有两个的话，将两个都加在3-4上，则最短路长11是最优的。,所以要是我们的加速设备增多一台的话，可能导致前面的所有放置方案都不是最优值。,例二 网络提速(经典问题),我们注意到一点，就是n和m都很小，特别是m，最大只有10。直觉和经验告诉我们，应该从数据规模小上面作文章。,从简单情形入手往往是解题的捷径。,没有m值，或者说m=0时，问题的解就是最简单的最短路径问题。m值的出现导致了最短路算法的失败。,关键是我们不知道应该在哪几条边用加速设备，而且每条边用多少次也不知道。方案与权值的分布还有m值的大小都有莫大的关联。,我们想想，有无m值的差异在哪，能够消除吗？,可以的。,例二 网络提速(经典问题),构造图G=(V,E)。设原图，将原图中的每个顶点vi拆成m+1个顶点，构造V使得：,对于原图的每一条边，注意是无向的，将它拆成(m+1)(m+2)条有向边：,构造E使得：,最后设定权函数w。对于，w满足：,例二 网络提速(经典问题),解释一下图G的含义。为了更清楚地说明问题，我们举出一个例子。下图(a)显示了某个G0(n=2,m=2)，按照以上的构造方法得出(b)中的G。将图G分成三层，第0层由顶点v1,0，v2,0构成，第1层由顶点v1,1，v2,1构成，第2层由顶点v1,2，v2,2构成。可以看出，若两个顶点间有边相连，两个顶点在同一层的，则顶点之间是互连的，若不在同一层，则层号小的顶点为边的起始点，层号大的为边的终点。,例二 网络提速(经典问题),层号代表已用的加速设备台数，例如从 到 需要且恰好要用一台加速设备。我们无法从层号大的顶点到达层号小的顶点，这符合同一个设备不能使用多次的规定。,顶点 到 的最短路长就是添置m台加速设备后计算机1到计算机n的最少传输时间。,剩下的工作就是对图G使用Dijkstra算法求 到 的最短路长。相信大家都会，我就不多说了。,结语,我们从理论上研究问题的最终目的是更好地指导实践。在题目中，往往不会直接告诉你，什么元素应该作为结点，什么元素应该作为边，应该如何构图。这就需要你根据题目的自身的特点，借鉴以往的解题经验，运用所学的相关知识，抽象出合适的模型，利用效率已有公论的算法高效求解。实际中遇到的题目可能千奇百怪，模型的转化千变万化，从而导致解法也多种多样，不拘一格，本文实在难以涵盖万一，只要能对读者有所启发，那么我的目的也就达到了。,最后送上两句话：,万变不离其宗。,阵而后战，兵法之常；运用之妙，存乎一心。,把握最短路的核心思想，合理转化模型,因地制宜，根据实际选择最合适的算法。,谢谢大家,