单源最短路径.pptxVIP

单源最短路径图论名词目录Bellman-Ford算法Dijkstra算法0201SPFA算法03基本信息给定一个带权有向图G=（V,E），其中每条边的权是一个实数。另外，还给定V中的一个顶点，称为源。要计算从源到其他所有各顶点的最短路径长度。这里的长度就是指路上各边权之和。这个问题通常称为单源最短路径问题。Dijkstra算法Dijkstra算法解决方案问题描述解题思想问题描述给定一个带权有向图 G=(V,E)，其中每条边的权是一个非负实数。另外，还给定 V中的一个顶点，称为源。我们要计算从源到所有其他各顶点的最短路径长度。这里的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。解决方案pascal：c++：c：解题思想将图G中所有的顶点V分成两个顶点集合S和T。以v为源点已经确定了最短路径的终点并入S集合中，S初始时只含顶点v,T则是尚未确定到源点v最短路径的顶点集合。然后每次从T集合中选择S集合点中到T路径最短的那个点，并加入到集合S中，并把这个点从集合T删除。直到T集合为空为止。具体步骤1、选一顶点v为源点，并视从源点v出发的所有边为到各顶点的最短路径（确定数据结构：因为求的是最短路径，所以①就要用一个记录从源点v到其它各顶点的路径长度数组dist,开始时，dist是源点v到顶点i的直接边长度，即dist中记录的是邻接阵的第v行。②设一个用来记录从源点到其它顶点的路径数组path,path中存放路径上第i个顶点的前驱顶点）。2、在上述的最短路径dist中选一条最短的，并将其终点（即<v,k>）k加入到集合s中。3、调整T中各顶点到源点v的最短路径。因为当顶点k加入到集合s中后，源点v到T中剩余的其它顶点j就又增加了经过顶点k到达j的路径,这条路径可能要比源点v到j原来的最短的还要短。调整方法是比较dist[k]+g[k,j]与dist[j]，取其中的较小者。4、再选出一个到源点v路径长度最小的顶点k,从T中删去后加入S中，再回去到第三步，如此重复，直到集合S中的包含图G的所有顶点。Bellman-Ford算法Bellman-Ford算法解题思想描述伪代码描述由于Dijikstra算法对于带负边权的图就无能为力了，但是Bellman-Ford算法就可以解决这个问题。解题思想算法基于动态规划，反复用已有的边来更新最短距离，Bellman-Ford算法的核心思想是松弛。如果dist[u]和dist[v]满足dist[v]>dist[u]+map[u][v],dist[v]就应该被更新为dist[u]+map[u][v]。反复的利用上式对dist数组进行松弛，如果没有负权回路的话，应当会在n-1次松弛后结束。伪代码s为源，map记录图的信息，map[u][v]为点u到v的边的长度，结果保存在dist；c：SPFA算法SPFA算法解题思想描述伪代码描述SPFA（Shortest Path Faster Algorithm）算法是求单源最短路径的一种算法，在Bellman-ford算法的基础上加上一个队列优化，减少了冗余的松弛操作，是一种高效的最短路算法。在 NOI2018Day1T1归程中正式被卡，其时间复杂度为O(nm)，远劣于Dijkstra的O((n+m)log m)。解题思想我们约定加权有向图G不存在负权回路，即最短路径一定存在。如果某个点进入队列的次数超过N次则存在负环（SPFA无法处理带负环的图）。当然，我们可以在执行该算法前做一次拓扑排序，以判断是否存在负权回路，但这不是我们讨论的重点。我们用数组d记录每个结点的最短路径估计值，而且用邻接表来存储图G。我们采取的方法是动态逼近法：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。定理:只要最短路径存在，上述SPFA算法必定能求出最小值。伪代码SPFA实际上是Bellman-Ford基础上的队列优化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) in E[G]7. Do tmp<-d[v]8. Relax(u,v,w)9. If (d[v] < tmp) and (v不在Q中)感谢观看