《最短路算法及其应用new》由会员分享，可在线阅读，更多相关《最短路算法及其应用new（23页珍藏版）》请在金锄头文库上搜索。
1、2006年全国信息学冬令营讲座最短路算法及其应用广东北江中学 余远铭【摘要】最短路问题是图论中的核心问题之一，它是许多更深层算法的基础。同时，该问题有着大量的生产实际的背景。不少问题从表面上看与最短路问题没有什么关系，却也可以归结为最短路问题。本文较详尽地介绍了相关的基本概念、常用算法及其适用范围，并对其应用做出了举例说明，侧重于模型的建立、思考和证明的过程，最后作出总结。【关键字】最短路【目录】一、基本概念211 定义212简单变体213负权边314重要性质及松弛技术4二、常用算法521 Dijkstra算法522 Bellman-Ford算法723 SPFA算法8三、应用举例1031 例题
2、1货币兑换1032 例题2双调路径1133 例题3Layout1334 例题4网络提速15四、总结18【正文】一、基本概念11 定义乘汽车旅行的人总希望找出到目的地尽可能短的行程。如果有一张地图并在地图上标出了每对十字路口之间的距离，如何找出这一最短行程？一种可能的方法是枚举出所有路径，并计算出每条路径的长度，然后选择最短的一条。然而我们很容易看到，即使不考虑含回路的路径，依然存在数以百万计的行车路线，而其中绝大多数是没必要考虑的。下面我们将阐明如何有效地解决这类问题。在最短路问题中，给出的是一有向加权图G=(V,E)，在其上定义的加权函数W:ER为从边到实型权值的映射。路径P=(v0, v1
3、, vk)的权是指其组成边的所有权值之和：定义u到v间最短路径的权为从结点u到结点v的最短路径定义为权的任何路径。在乘车旅行的例子中，我们可以把公路地图模型化为一个图：结点表示路口，边表示连接两个路口的公路，边权表示公路的长度。我们的目标是从起点出发找一条到达目的地的最短路径。边的权常被解释为一种度量方法，而不仅仅是距离。它们常常被用来表示时间、金钱、罚款、损失或任何其他沿路径线性积累的数量形式。12简单变体单目标最短路径问题： 找出从每一结点v到某指定结点u的一条最短路径。把图中的每条边反向，我们就可以把这一问题转化为单源最短路径问题。单对结点间的最短路径问题：对于某给定结点u和v，找出从u
4、到v的一条最短路径。如果我们解决了源结点为u的单源问题，则这一问题也就获得了解决。对于该问题的最坏情况，从渐进意义上看，目前还未发现比最好的单源算法更快的方法。每对结点间的最短路径问题：对于每对结点u和v，找出从u到v的最短路径。我们可以用单源算法对每个结点作为源点运行一次就可以解决问题。13负权边在某些单源最短路问题中，可能存在权为负的边。如果图G(V,E)不包含由源s可达的负权回路，则对所有，最短路径的权的定义依然正确。即使它是一个负值也是如此。但如果存在一从s可达的负权回路，最短路径的定义就不能成立了。从s到该回路上的结点不存在最短路径因为我们总可以顺着找出的“最短”路径再穿过负权回路从
5、而获得一权值更小的路径，因此如果从s到v的某路径中存在一负权回路，我们定义。图1 含有负权和负权回路的图图1说明负的权值对最短路径的权的影响。每个结点内的数字是从源点s到该结点的最短路径的权。因为从s到a只存在一条路径(路径)，所以：。类似地，从s到b也只有一条通路，所以：。从s到c则存在无数条路径：,等等。因为回路的权为6+(-3)=30，所以从s到c的最短路径为，其权为：。类似地，从s到d的最短路径为，其权为：。同样，从s到e存在无数条路径：,等等.由于回路的权为3+(-6)=-30，所以从s到e没有最短路径。只要穿越负权回路任意次，我们就可以发现从s到e的路径可以有任意小的负权值，所以：
6、类似地，因为g是从f可达的结点，我们从s到g的路径可以有任意小的负权值，则：。结点h，j，i也形成一权值为负的回路，但因为它们从s不可达，因此。一些最短路径的算法，例如Dijkstra算法，都假定输入图中所有边的权取非负数，如公路地图实例。另外一些最短路算法，如Bellman-Ford算法，允许输入图中存在权为负的边，只要不存在从源点可达的权为负的回路，这些算法都能给出正确的解答。特定地说，如果存在这样一个权为负的回路，这些算法可以检测出这种回路的存在。14重要性质及松弛技术本文的算法所运用的主要技术是松弛技术，它反复减小每个结点的实际最短路径的权的上限，直到该上限等于最短路径的权。让我们看看
7、如何运用松弛技术并正式证明它的一些特性。定理1 (最优子结构) 给定有向加权图G=(V,E)，设P=为从结点v1到结点vk的一条最短路径，对任意i,j有i=j=k，设Pij=为从vi到vj的P的子路径,则Pij是从vi到vj的一条最短路径。证明：我们把路径P分解为。则w(P)=w(P1i)+w(Pij)+w(Pjk)。现在假设从vi到vj存在一路径Pij，且w(Pij)du+w(u,v)2. Then dvdu+w(u,v)3. vu图2 对边(u,v)进行松弛图2说明了松弛一条边的两个实例，在其中一个例子中最短路径估计减小，而在另一实例中最短路径估计不变。(a)因为在进行松弛以前dvdu+w
8、u,v，所以dv的值减小。(b)因为松弛前dv=0。Dijkstra算法中设置了一结点集合S，从源结点s到集合S中结点的最终最短路径的权均已确定，即对所有结点vS，有dv=(s,v)。算法反复挑选出其最短路径估计为最小的结点uV-S，把u插入集合S中，并对离开u的所有边进行松弛。在下列算法实现中设置了优先队列Q，该队列包含所有属于V-S的结点，且队列中各结点都有相应的d值。算法假定图G由临接表表示。Dijkstra(G,w,s)1. INITIALIZE-SINGLE-SOURCE(G,S)2. S3. QVG4. While Q5. Do uEXTRACT-MIN(Q)6. SS Uu7.
9、For 每个顶点vAdju8. Do RELAX(u,v,w)Dijkstra算法如图3所示对边进行松弛操作，最左结点为源结点，每个结点内为其最短路径估计。图3 Dijkstra算法的执行流程阴影覆盖的边说明了前驱的值：如果边(u,v)为阴影所覆盖，则v=u。黑色结点属于集合S，白色结点属于优先队列Q=V-S。第1行对d和值进行通常的初始化工作。第2行置集合S为空集。第3行对优先队列Q进行初始化使其包含V-S=V-=V中的所有结点。每次执行第4-8行的While循环时，均从队列Q=V-S中压出一结点u并插入到集合S中(第一次循环时u=s)。因此在V-S中的所有结点中，结点u具有最小的最短路径估
10、计。然后，第7-8行对以u为起点的每条边(u,v)进行松弛。如果可以经过u来改进到结点v的最短路径,就对估计值dv以及先辈v进行更新。注意在第3行以后就不会再插入结点到Q中，并且每个结点只能从Q弹出并插入S一次，因此第4至8行的While循环的迭代次数为|V|次。因为Dijkstra算法总是在集合V-S中选择“最轻”或“最近”的结点插入集合S中，因此我们说它使用了贪心策略。需要指出的是，贪心策略并非总能获得全局意义上的最理想结果。但Dijkstra算法确实计算出了最短路径，关键是要证明：定理2 每当结点u插入集合S时，有du=(s,u)成立。简证：我们每次选择在集合V-S中具有最小最短路径估计
11、的结点u，因为我们约定所有的边权值非负，所以有可能对结点u进行松弛操作的结点必不在集合V-S中（否则与结点u的定义矛盾），因此只会在集合S中。又由于我们选取结点进入S时，S中的结点已全部进行过松弛操作了，所以du的值不会再发生改变。因此du=(s,u)。（证毕）我们最关注的问题是：Dijkstra算法的执行速度如何？首先我们考虑用一维数组来实现优先队列Q=V-S的情形。在该算法的实现下，每次EXTRACT-MIN操作运行时间为O(V)，存在|V|次这样的操作，所以EXTRACT-MIN的全部运行时间为O(V2)。因为每个结点vV仅被插入集合S一次，所以在算法的执行过程中邻接边Adjv中的每条边在第4-8行的For循环中仅被考察一次。因为在所有邻接表中边的总数为|E|，所以在该For循环中总共存在|E|次迭代，每次迭代运行时间为O(1)，因此整个算法的运行时间为O(V2+E)=O(V2)。但在稀疏图的情形下，用二叉堆来实现优先队列Q是比较实用的。在该算法实现下，每个EXTRACT-MIN操
