Shortest Path

单源最短路径，即计算一个节点到其它所有节点的最短路径

这类算法的基础是松弛(relax)操作，即对于边权为c的(u, v)

dis[v] = min(dis[v], dis[u] + c);

Dijkstra¶

算法思想即将其余点分为确定了最短路径和没有确定最短路径两个集合，每次从没有确定的部分中选出距离最短的一个点，以当前距离作为最短距离，将这个点加入已经确定距离的集合中

算法要求是图中没有负权边，因为每次选距离最近的未确定点加入确定集合，依据是出发点到这个点的距离在之后不会再变动，但如果有负权边，这个距离之后还可能变，所以算法会不成立

对于点少边多的稠密图，可以写成 $O(V^2)$ 的算法，外层循环V-1次，每次选还没有确定距离的点里距离最近的一个点，确定距离，并对这个点相连的边进行松弛

对于点多边少的稀疏图，可以实现为 $O(V+ElogV)$ 的算法，即用一个优先级队列来完成每次选取最小距离的操作，复杂度可以这样想，外围循环是O(V)，每次取出最小元素O(logV)，之后松弛操作平均执行E/V次，每次更新优先级队列复杂度为O(logV)，总体复杂度为V(logV+E/V*logV)=ElogV，因为E一定大于等于V，其实这里开头的V可以省去，基本是 $O(ElogV)$ 的算法

实际C++实现可以用优先级队列，更新时不改原来值，而是加入多个同样节点，每个节点距离不同，在取队首元素时如果发现该元素已经在之前确定了距离，直接pop掉，如此操作队列长为E*V/V=E，复杂度实际是 $O(ElogE)$ ，但 $logE$ 和 $logV$ 其实是一个量级，所以相差不大

用fibonacci堆，可以优化到 $O(E+VlogV)$

SPFA (Bellman-Ford)¶

这两个算法可以对有负边没有负环的图求单源最短路

Bellman-Ford算法思路很简单，因为一条简单路径最长为V-1，所以循环V-1次，每次遍历所有边，进行松弛，最后所得结果就是起点到所有点的最短路

这个算法也可以用来判断图中有没有负环，即在完成上述V-1次松弛后，再遍历所有边松弛一次，如果还有边可以进行松弛，说明存在负环

SPFA (Shortest Path Faster Algorithm)是对BF算法的改进，思路是将所有成功松弛过的点放入一个队列，每次从取出队首元素，然后对其相应边进行松弛操作，将成功松弛且不在队列中的点加入队列

重复操作直到队列为空，即可得到起点到每个点的路径长度

SPFA同样可以判断图中是否存在负环，方法是记录每个点的松弛次数，一个点松弛次数等于V时，说明存在负环

Floyd¶

Floyd算法计算的是所有结点对之间的最短路径，复杂度是 $(V^3)$