引出
在我们平时图中找最短路径的时候，总是用搜索来做
但是 DFS 时间复杂度太高，相当于暴力的做法
BFS，虽然相对于 DFS 时间复杂度较低
但是只能处理边权为相同的图
这是，我们可以使用一种新的算法——最短路径
Floyd 算法
采用动态规划的思想。假设对每对 (s,t) 已经知道了 s 只经过编号在 [1,i] 间的节点到达 t 的最短路径长度。
每对点之间的距离会如何变化：我们只需要考虑经过点 i+1 的路径对每对点距离的影响。
考虑 s 经过 i+1 到 t 的路径时，s 到 i+1 这段只用考虑最短的路径，i+1 到 t 同理。
也就是只用考虑 \text{dis}(s,i+1)+\text{dis}(i+1,t) 是否小于 \text{dis}(s,t)。如果是，就用它更新 \text{dis}(s,t)。一次这个操作称为松弛。
那么算法的过程就是：
- 枚举每个点 i；
- 枚举每个点对 (s, t)；
- 用 \text{dis}(s, i) + \text{dis}(i, t) 更新 \text{dis}(s, t)。
注意初始化的时候，\text{dis}(s, t) 就是两点之间的边权。如果没有边则设为 +\infty。时间复杂度为 O(n^3)，空间复杂度为 O(n^2)。
单源最短路
给定带权图 G(V, E) 和指定起点 s，求 s 到所有点的最短路。
Bellman-Ford 算法
先考虑图中没有负环（节点 u 到自己的一条路径，长度小于 $0$）的情况。
图中没有负环，则最短路中没有环。
考虑反证法。如果最短路中有环，则这个环必然长度 \geq 0。去掉这个环后，可以得到一条长度不比原来长的路径。
由于最短路中没有环，因此最短路中每个点只会被经过一次。因此最短路的边数最多是 n-1。
因此考虑进行 n - 1 轮松弛。每次枚举一条边 e，用 s 到 u_e 的已知最短路和这条边，去更新 s 到 v_e 的最短路。
也就是用 \text{dis}(s, u_e) + w_e 去更新 \text{dis}(s, v_e)。
算法的时间复杂度为 O(nm)。
当图中有负环的时候，依照定义环上的点之间距离是 -\infty。
那么必然在每一轮都会产生成功的松弛操作。
而没有负环的图，从第 n 轮开始就不会产生成功的松弛操作。
因此可以通过第 n 轮是否有松弛操作来判断图中是否存在负环。
SPFA
{SPFA 算法——优化的 Bellman-Ford}
- 使用队列优化松弛操作，只对距离更新的节点进行处理。
- 如果一个节点被松弛超过 |V| 次，则存在负环。
- 时间复杂度：平均 O(E)，最坏 O(VE)。
Dijkstra 算法
Dijkstra 算法是一个基于以下引理的更快的非负权图单源最短路算法：
引理 不妨假设图连通。如果已知距离起点 s 最近的 $k$（$1 \leq k < n$）个点（设为点集 $S$），则距离 s 第 k + 1 近的点，必然是 S 中某个点 u 的邻居 v，满足 \exists e \in [1, m], u = u_e, v = v_e, \text{dis}(u_e) + w_e 最小。
证明 首先一个不是 S 的邻居的点必定不是第 k + 1 近的点。考虑反证法，假设不是邻居的点是第 k + 1 近的点。取 s 到这个点的最短路上第一个不是 k 个点的点，取出的的点必然是 S 的邻居，且 s 到这个点的距离更近。
其次，所有 \text{dis}(u_e) + w_e 不是最小的 v_e，s 到它们的最短路径必然大于等于最小的 \text{dis}(u_e) + w_e。同样考虑反证，用上面的取点方法，可以找到一个更小的 \text{dis}(u_e) + w_e 的值。
基于这个引理，我们可以设计如下算法：
- 用一个优先队列维护所有的 (dis(u_e) + w_e, v_e) 对；
- 取出键值最小的一个加入 S；
- 更新优先队列（将取出的点 u 的邻居 v_e 加入）。
要注意，首先，我们只在这个值能松弛 v_e 的最短路的时候将 v_e 加入优先队列。其次，尽管如此，一个点还是有可能入队多次，我们只认可它第一次被弹出的时候。
由于每条边最多被遍历一次，每次都有可能被插入堆，算法的复杂度是 O(m \log m)。要注意：
- Dijkstra 不能正确处理带负权边的情况。
- 注意
std::priority_queue默认是大根堆。 - 要先弹出堆顶，再检查是否需要跳过。
- 插入堆的
std::pair第一维需要是距离。 - 距离可能会爆
int。
除此之外，当图比较稠密的时候，可以直接进行 n 轮暴力挑选最小距离点，不需要用堆。这样复杂度是 O(n^2 + m)，当 n^2 = O(m) 的时候这样更划算。
最短路树
在单源最短路径的过程中，每个点 v 都存在一些前驱 u，满足 \text{dis}(u) + w(u,v) = \text{dis}(v)，这里 w(u,v) 是 u, v 两点之间最短的一条边的边权。
如果我们得到一棵树，根节点为单源最短路径的起点 s，树上每个节点的父亲都是它的某个前驱，则起点到每个点的最短距离，就是这棵树上这个节点到根路径的长度。
这样的树就被称作最短路径树。
要得到最短路树，首先需要知道每个点的前驱。
在 Dijkstra 的过程中，我们只需要记录每个点 v 最后一次被松弛的时候是被哪个点 u 松弛的，则这个 u 就是 v 的前驱。
然后把每个节点的父亲设置成它的前驱就行了。
注意到这样做必定是没有问题的。因为将节点出队顺序看作一个拓扑序，节点之间的前驱关系是符合这个拓扑序的。也就是说每个点的前驱必然比它早出队。因此即使图上有零权环也没关系。