单源最短路径

图论名词

给定一个带权有向图G=（V,E），其中每条边的权是一个实数。另外，还给定V中的一个顶点，称为源。要计算从源到其他所有各顶点的最短路径长度。这里的长度就是指路上各边权之和。这个问题通常称为单源最短路径问题。

Dijkstra算法

问题描述

给定一个带权有向图 G=(V,E) ，其中每条边的权是一个非负实数。另外，还给定 V 中的一个顶点，称为源。我们要计算从源到所有其他各顶点的最短路径长度。这里的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。

解决方案

Dijkstra提出按各顶点与源点v间的路径长度的递增次序，生成到各顶点的最短路径的算法。既先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从源点v 到其它各顶点的最短路径全部求出为止。

解题思想

将图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[ ]中选一条最短的，并将其终点（即）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的所有顶点。

示例代码

pascal：

c++：

c：

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（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中)