最短路径问题.

最短路径问题基本概念•最短路径问题的3种类型1.单源最短路径问题：找出从每一节点v到某指定节点u的一条最短路径。把图中的每条边反向，我们就可以把这一问题转化为单源最短路径问题。2.单对节点间的最短路径问题：对于给定节点对u和v，找出从u到v的一条路径。3.每对节点间的最短路径问题：对于每对节点u和v，找出从u到v的最短路径。可以使用Floyed-Warshall算法解决问题，但时间效率底下，且有不能出现负权回路的苛刻条件。不妨以每个节点为源点运行一次单源算法，以提高时效。松弛技术是单源算法的核心•所谓松弛技术，就是反复减小每个节点的实际最短路径的权的上限，直到该上限等于最短路径的权为止。•定理：给定有向加权图G=（V，E），设P=V1,V2,……,Vk为从节点V1到节点Vk的一条路径，对任意i，j有i=j=k，设Pij=Vi,Vi+1,…,Vj为Vi到Vj的P的子路径，则Pij是从Vi到Vj的一条最短路径。•给定有向加权图G=（V，E），源点为s，则对于所有边（u,v）∈E，有&（s，v）=&（s，u）+w（u,v）。松弛技术•对每个节点v∈V，设置一个属性d[v]来描述从源点s到v的最短路径的权的上界，称之为最短路长估计，设置f[v]表示v点的父亲。Procinitiallze_single_source(G,s);{foreachv∈V[G]do{d[v]:=∞;f[v]=nil;}d[s]:=0;}•松弛一条边（u,v）的过程包括测试是否可通过节点u对目前找出的到v的最短路径进行改进，如果可能则更新d[v]和f[v]，一次松弛操作可以减小最短路长估计d[v]并更新v的父亲f[v]。Procrelax(u,v,w);{ifd[v]d[u]+w[u,v]then{d[v]:=d[u]+w[u,v];f[v]:=u;}}Dijkstra算法•Dijkstra算法解决了有向加权图的最短路径问题，该算法的条件是该图所有边的权值非负，即对于每条边(u,v)∈E，w(u,v)=0;•Dijkstra算法中设置了一节点集合S，从源节点r到集合S中节点的最终最短路径的权均已确定，即对所有节点v∈S，有d[v]=&(r,v)，并设置了最小优先队列Q，该队列包含所有属于V-S的节点（即这些节点尚未确定最短路径的权），且以d值为关键字排列各节点。•初始时，Q包含了除r外的其他节点，这些节点的d值为∞。r进入集合S，d[r]=0。算法反复从Q中取出d值最小的节点u∈V-S，把u插入集合S中，并对u的所有出边进行松弛。这一过程一直进行到Q队列为空为止。只要图中没有负权边，Dijkstra算法能够顺利完成。如果任何一条边的权值为负，则算法可能得出错误的答案。ProcedureDijstra(G,w,r);{initiallze_single_source(G,r);S:=∮;Q:=V[G];whileQ∮do{从最小优先队列Q中取出d值最小的节点u；S:=S∪[u];forv∈adj(u)dorelax(u,v,w);}}Dijkstra算法的执行速度取决于优先队列Q的数据结构。有3种数据结构可供选择：（1）用一维数组实现优先队列，时间复杂度为O（V*V）。使用于规模不大的稠密图。（2）用二叉堆来实现优先队列Q，时间复杂度为O（ElnV），使用于稀疏图。（3）用Fibonacci堆实现优先队列，时间复杂度优化为O（VlnV+E）。但Fibonacci堆的程序实现相当繁琐，程序的实际运行效果不理想，不推荐使用。Dijkstra算法与Prim算法的异同：同：都是属于宽度优先搜索，且优先队列Q都是以距离d为关键字排列的，节点出队后都要进行松弛操作。异：Dijkstra算法中的距离d是节点与源点间最短路长估计值，Prim算法中的距离d是节点连接生成树的最短边长。变形•求出最短路的路径•对于多条最短路存在的情况，求方案数•求次短路径Dijkstra•P1398Car的旅行路线•P1577最佳路线•Poj3013BigChristmasTree•Poj1135DominoEffect负权回路影响单源最短路径的计算•在某些单源最短路径问题中，可能存在权为负的边。如果图G（V,E）不包含由源s可达的负权回路，则对所有v∈Vs，最短路径的权的定义&(s,v)依然正确，即使它是一个负值也是如此。但如果存在一个从s可达的负权回路，最短路径的定义就不能成立了。从s到该回路上的节点不存在最短路径，因为我们总可以顺着找出的“最短”路径再穿过负权回路，从而获得一个权值更小的路径，因此如果从s到v的某路径中存在一个负权回路，我们定义&(s,v)=-∞。Bellman-Ford算法Bellman-Ford算法能在更一般的情况下解决单源点最短路径问题，在该算法中边的权可以为负。Bellman-Ford算法同样运用了松弛技术，对每一节点v∈V，逐步减小从源s到v的最短路长估计d[v]直至其达到实际最短路径的权&(s,v)，如果图中存在负权回路，算法将会报告最短路径不存在。算法时间O（VE）。FuncBellman_Ford(G,w,s):boolean;{initiallze_single_source(G,s);fori:=1to|V|-1doforeach(u,v)∈Edorelax(u,v,w);foreach(u,v)∈Edoifd[v]d[u]+w(u,v)thenexit(false);exit(true);}Bellman-Ford算法的思想基于以下事实：两点间如果有最短路径，那么每个节点最多经过一次。也就是说，这条路不超过n-1条边。如果一个节点经过了两次，那么就是走了一个圈。如果这个圈的权为正，显然不划算；如果是负圈，那么最短路径不存在。如果是零圈，去掉不影响最优值。Bellman-Ford•Zoj1456MinimumTransportCostSPFA算法•SPFA算法全称是ShortestPathFasterAlgorithm。•Dijkstra不能解决负权边，Bellman-Ford算法效率底，可使用SPFA算法。•与Dijkstra算法和Bellman-Ford算法一样，用数组d记录每个节点的最短路长估计，并且用邻接表来存储图G。•采用动态逼近的方法：设立一个先进先出的队列Q，用来保存待优化的节点，优化时每次取出队首节点u，并且用u点当前的最短路长估计对u点出边所指向的节点v进行松弛操作，如果v点的最短路长估计有所调整，且v点不在当前的队列中，就将v点放入Q队的队尾。这样不断从队列Q中取出节点来进行松弛操作，直至Q队列空为止。SPFA算法ProcSPFA(G,w,s);{initiallze_single_source(G,s);队列Q初始化为空;源点s入队列Q;whileQ队列非空do{从Q中取出队首节点u;foreachv∈u相邻的节点集do{tmp:=d[v];relax（u,v,w);if(d[v]tmp)and(v不在Q内)thenv进入Q队尾;}}}SPFA算法的期望时间复杂度为O(E)。思考：怎么判断负权回路？SPFA算法与Bellman-Ford算法比较•同：两者都属于标号修正的范畴，计算过程都是迭代式的，最短路长估计值都是临时的，都采用了不断逼近最优解的贪心策略，只在最后一步才确定想要的结果。•差异：在Bellman-Ford算法中，要是某个点的最短路长估计值被更新了，那么就必须对所有边的尾做一次松弛操作；在SPFA算法中，某个点的最短路径估计值被更新，仅需要对该点出边的端点做一次松弛操作。spfa•P1358Easysssp•P1561想越狱的小杉•P1421集合位置•P1543冰原探险•P1670热浪Floyd_Warshall算法•求任意两点间的最短路问题•DP求解：•设f[k,I,j]为在使用0~k的顶点时Vi到Vj的距离，初始时f[0,I,j]=cost[I,j]。•不断插入顶点k。•如果Vi和Vj的最短路不经过k,则f[k,I,j]=f[k-1,I,j]•如果Vi和Vj的最短路经过k，则f[k,I,j]=f[k-1,I,k]+f[k-1,k,j]•合起来就是：F[k,I,j]=min(f[k-1,I,j],f[k-1,I,k]+f[k-1,k,j])•状态压缩后：f[I,j]=min(f[I,j],f[I,k]+f[k,j])•时间复杂度为O（V^3），如果图中有负圈，只需检查是否存在d[I,i]是负数即可Floyed-Warshall算法初始时，longpath存储有向图的相邻矩阵，path存储边信息;fillchar(longpath,sizeof(longpath),-∞);fillchar(path,sizeof(path),0);foreachi∈vdoforeachj∈vdoif(i,j)∈ethen{longpath[i,j]:=wij;path[i,j]:=i;};foreachk∈vdoforeachi∈vdoforeachj∈vdoiflongpath[i,k]+longpath[k,j]longpath[i,j]then{longpath[i,j]:=longpath[i,k]+longpath[k,j];path[i,j]:=path[k,j];};输出路径procedureprint(i,j);{ifi=jthen输出ielseifpath[i,j]=0then输出节点i与节点j之间不存在通路else｛print(i,path[i,j]);输出j;｝}•P1234挖地雷•P1592最短路上的统计•P1694cowtour•P1353观光旅游•POJ2253Frogger•POJ2240Arbitrage•POJ2243KnightMoves•POJ1125StockbrokerGrapevine•POJ2472106milestoChicago传递闭包的应用•传递闭包longlink的计算过程foreachk∈vdoforeachi∈vdoforeachj∈vdolonglink[i,j]:=longlink[i,j]or(longlink[i,k]andlonglink[k,j]);传递闭包的应用•（1）利用传递闭包计算连通分量和有向无圈图的根•（2）利用传递闭包计算“缩图”•（3）基于传递闭包思想的Floyed-Warshall算法利用传递闭包计算连通分量和有向无圈图的根•在无向图的longlink矩阵中，每行（列）中值为true的元素代表对应节点所在的连通分量，含true最多的行对应一个节点数最多的连通分支。•在有向图的longlink矩阵中，若r行元素值除r列外为true，则r到其他任何节点都有路，即r为有向无圈图的根利用传递闭包计算“缩图”对有向图而言，利用longlink矩阵可方便地计算每个节点所在的强连通分量和强连通分量被缩成节点后的“缩图（scc）”。设sblg[v]为节点v所在的强连通分量序号，“缩图”的相邻矩阵为anet，其中anet[I,j]标志强连通分量i和强连通分量j之间的连接关系。计算有向图g的传递闭包longlink;n1:=0;fillchar(sblg,sizeof(sblg),0);foreachi∈vdoifsblg[i]=0then{inc(n1);sblg[i]:=n1;foreachj∈vdoiflonglink[i,j]andlonglink[j,i]thensblg[j]:=n1;}fillchar(anet,sizeof(anet),0);foreachi∈vdoforeachj∈vdoif(sblg[i]sblg[j])and(notanet[sblg[i],sblg[j])thenanet[sblg[i],sblg[j]]:=longlink[i,j];差分约束系统•差分约束系统（systemofdifferenceconstraints）是线性规划问题的一种。在一个差分约束系统中，线性规划矩阵A的每一行