最短路径问题

1、最短路径问题基本概念最短路径问题的3种类型1.单源最短路径问题：找出从每一节点v到某指定节点u的一条最短路径。把图中的每条边反向，我们就可以把这一问题转化为单源最短路径问题。2.单对节点间的最短路径问题：对于给定节点对u和v，找出从u到v的一条路径。3.每对节点间的最短路径问题：对于每对节点u和v，找出从u到v的最短路径。可以使用Floyed-Warshall算法解决问题，但时间效率底下，且有不能出现负权回路的苛刻条件。不妨以每个节点为源点运行一次单源算法，以提高时效。松弛技术是单源算法的核心 所谓松弛技术，就是反复减小每个节点的实际最短路径的权的上限，直到该上限等于最短路径的权为止。 定理：

2、给定有向加权图G=（V，E），设P=为从节点V1到节点Vk的一条路径，对任意i，j有i=j=k，设Pij=为Vi到Vj的P的子路径，则Pij是从Vi到Vj的一条最短路径。 给定有向加权图G=（V，E），源点为s，则对于所有边（u,v）E，有&（s，v）du+w if dvdu+wu,vu,v then dv:=du+w then dv:=du+wu,vu,v;fv:=u;fv:=u; Dijkstra算法 Dijkstra算法解决了有向加权图的最短路径问题，该算法的条件是该图所有边的权值非负，即对于每条边(u,v)E，w(u,v)=0; Dijkstra算法中设置了一节点集合S，从源节

3、点r到集合S中节点的最终最短路径的权均已确定，即对所有节点vS，有dv=&(r,v)，并设置了最小优先队列Q，该队列包含所有属于V-S的节点（即这些节点尚未确定最短路径的权），且以d值为关键字排列各节点。 初始时，Q包含了除r外的其他节点，这些节点的d值为。r进入集合S，dr=0。算法反复从Q中取出d值最小的节点uV-S，把u插入集合S中，并对u的所有出边进行松弛。这一过程一直进行到Q队列为空为止。只要图中没有负权边，Dijkstra算法能够顺利完成。如果任何一条边的权值为负，则算法可能得出错误的答案。Procedure Dijstra(G,w,r); initiallze_singl

4、e_source(G,r); S:=;Q:=VG; while Q do 从最小优先队列Q中取出d值最小的节点u； S:=Su; for vadj(u) do relax(u,v,w); Dijkstra算法的执行速度取决于优先队列Q的数据结构。有3种数据结构可供选择：（1）用一维数组实现优先队列，时间复杂度为O（V*V）。使用于规模不大的稠密图。（2）用二叉堆来实现优先队列Q，时间复杂度为O（ElnV），使用于稀疏图。（3）用Fibonacci堆实现优先队列，时间复杂度优化为O（VlnV+E）。但Fibonacci堆的程序实现相当繁琐，程序的实际运行效果不理想，不推荐使用。Dijkstra算

5、法与Prim算法的异同：同：都是属于宽度优先搜索，且优先队列Q都是以距离d为关键字排列的，节点出队后都要进行松弛操作。异：Dijkstra算法中的距离d是节点与源点间最短路长估计值，Prim算法中的距离d是节点连接生成树的最短边长。变形 求出最短路的路径 对于多条最短路存在的情况，求方案数 求次短路径Dijkstra P1398 Car的旅行路线 P1577 最佳路线 Poj 3013 Big Christmas Tree Poj 1135 Domino Effect负权回路影响单源最短路径的计算 在某些单源最短路径问题中，可能存在权为负的边。如果图G（V,E）不包含由源s可达的负权回路，则对

6、所有vVs，最短路径的权的定义&(s,v)依然正确，即使它是一个负值也是如此。但如果存在一个从s可达的负权回路，最短路径的定义就不能成立了。从s到该回路上的节点不存在最短路径，因为我们总可以顺着找出的“最短”路径再穿过负权回路，从而获得一个权值更小的路径，因此如果从s到v的某路径中存在一个负权回路，我们定义&(s,v)=-。Bellman-Ford算法Bellman-Ford算法能在更一般的情况下解决单源点最短路径问题，在该算法中边的权可以为负。Bellman-Ford算法同样运用了松弛技术，对每一节点vV，逐步减小从源s到v的最短路长估计dv直至其达到实际最短路径的权&

7、;(s,v)，如果图中存在负权回路，算法将会报告最短路径不存在。算法时间O（VE）。Func Bellman_Ford(G,w,s):boolean;initiallze_single_source(G,s); for i:=1 to |V|-1 do for each(u,v)E do relax(u,v,w); for each(u,v)E do if dvdu+w(u,v) then exit(false); exit(true);Bellman-Ford算法的思想基于以下事实：两点间如果有最短路径，那么每个节点最多经过一次。也就是说，这条路不超过n-1条边。如果一个节点经过了两次，那么

8、就是走了一个圈。如果这个圈的权为正，显然不划算；如果是负圈，那么最短路径不存在。如果是零圈，去掉不影响最优值。Bellman-Ford Zoj 1456 Minimum Transport CostSPFA算法 SPFA算法全称是Shortest Path Faster Algorithm。 Dijkstra不能解决负权边，Bellman-Ford算法效率底，可使用SPFA算法。 与Dijkstra算法和Bellman-Ford算法一样，用数组d记录每个节点的最短路长估计，并且用邻接表来存储图G。 采用动态逼近的方法：设立一个先进先出的队列Q，用来保存待优化的节点，优化时每次取出队首节点u，并

9、且用u点当前的最短路长估计对u点出边所指向的节点v进行松弛操作，如果v点的最短路长估计有所调整，且v点不在当前的队列中，就将v点放入Q队的队尾。这样不断从队列Q中取出节点来进行松弛操作，直至Q队列空为止。SPFA算法Proc SPFA(G,w,s); initiallze_single_source(G,s); 队列Q初始化为空; 源点s入队列Q; while Q队列非空 do 从Q中取出队首节点u; for each vu相邻的节点集 do tmp:=dv;relax（u,v,w); if (dvlongpathi,j then longpathi,j:=longpathi,k+longpa

10、thk,j; pathi,j:=pathk,j;输出路径procedure print(i,j);if i=j then 输出i else if pathi,j=0 then 输出节点i与节点j之间不存在通路 else print(i,pathi,j);输出j; P1234 挖地雷 P1592 最短路上的统计 P1694 cowtour P1353观光旅游 POJ 2253 Frogger POJ 2240 Arbitrage POJ 2243 Knight Moves POJ 1125 Stockbroker Grapevine POJ 2472 106 miles to Chicago传递

11、闭包的应用传递闭包longlink的计算过程for each kv do for each iv do for each jv do longlinki,j:=longlinki,j or (longlinki,k and longlinkk,j);传递闭包的应用 （1）利用传递闭包计算连通分量和有向无圈图的根 （2）利用传递闭包计算“缩图” （3）基于传递闭包思想的Floyed-Warshall算法利用传递闭包计算连通分量和有向无圈图的根 在无向图的longlink矩阵中，每行（列）中值为true的元素代表对应节点所在的连通分量，含true最多的行对应一个节点数最多的连通分支。 在有向图的l

12、onglink矩阵中，若r行元素值除r列外为true，则r到其他任何节点都有路，即r为有向无圈图的根利用传递闭包计算“缩图”对有向图而言，利用longlink矩阵可方便地计算每个节点所在的强连通分量和强连通分量被缩成节点后的“缩图（scc）”。设sblgv为节点v所在的强连通分量序号，“缩图”的相邻矩阵为anet，其中anetI,j标志强连通分量i和强连通分量j之间的连接关系。计算有向图g的传递闭包longlink;n1:=0;fillchar(sblg,sizeof(sblg),0);for each i v do if sblgi=0 then inc(n1);sblgi:=n1; for

13、 each jv do if longlinki,j and longlinkj,i then sblgj:=n1;fillchar(anet,sizeof(anet),0);for each i v do for each jv do if (sblgisblgj) and (not anetsblgi,sblgj) then anetsblgi,sblgj:=longlinki,j;差分约束系统 差分约束系统（system of difference constraints）是线性规划问题的一种。在一个差分约束系统中，线性规划矩阵A的每一行包含一个1和一个-1，A的所有其他元素都为0。因此

14、，由Axb给出的约束条件是m个差分约束集合，其中包含n个未知元。每个约束条件为如下形式的简单线性不等式：xj-xibk,其中，1i, jn，1km。例如：寻找一个5维向量x = ( xi )以满足如下左图约束条件，这一问题等价于找出未知量x1，x2，x3，x4，x5，满足右图的8个差分约束条件： 该问题的一个解为x = ( -5, -3, 0, -1, -4)，这可以直接代入每个不等式得到验证。实际上，该问题有多个解。另一个解为x = ( 0, 2 , 5, 4, 1)，这两个解是有联系的：x中的每个元素比x中的相应元素大5。这一事实并不是巧合：若x = ( x1, x2, , xn )是一个

15、差分约束系统Axb的一个解，d为任意常数。则x + d = ( x1 + d, x2 + d, , xn + d )也是该系统Axb的解。 对于每个xi和xj，有( xj + d ) - ( xi + d ) = xj - xi。因此，若x满足Axb，则x + d也同样满足。例如：寻找一个5维向量x = ( xi )以满足如下左图约束条件，这一问题等价于找出未知量x1，x2，x3，x4，x5，满足右图的8个差分约束条件：差分约束系统算法思想 每一个约束条件的不等式与求单源最短路算法中的松弛操作（dv=du+wu,v，即dv-du=wu,v）极为类似。 将图形理论与差分约束系统Axb加以联系：m

16、 * n的线性规划矩阵A可被看作是n个顶点，m条边的图的关联矩阵的转置。对于i = 1, 2, , n，图中的每一个顶点vi对应着n个未知量的一个xi。图中的每个有向边对应于两个未知量的m个不等式的其中一个。这样，通过求解新建立图的单源最短路经问题就能得到差分约束系统的一组解。 为保证图的连通，在图中引入附加节点vs使图中每个顶点vi都能从vs可达，并设弧( vs, vi )的权w( vs, vi ) = 0。对于每一个差分约束xj - xi bk(注意是小于等于符号)，则弧( xi, xj )的权w( xi, xj ) = bk。初始化dis vs = 0，dis i = 。求解以vs为源点的单源最短路径。如果图中存在负权回路，则该差分约束系统不存在可行解。 值得注意的是：虽然顶点虽然顶点v