最短路
最短路问题一般在带权图中考虑。
最短路问题中，无向图与有向图类似，将一条无向边拆成两条权值相同，方向相反的边。
最短路类型：
- 单源最短路：一个起点。
- 多源最短路：多个起点（共用一个最短路距离）。
- 全源最短路：任意两点之间的最短路。
松弛：
对 $(u,v,w)$ 进行松弛：dis[v]=min(dis[v],dis[u]+w)
Dijkstra：
一种用于求非负权图上单源最短路径的算法。
过程：
将节点分成两个集合：
- 已确定最短路长度的点集（S）
- 未确定最短路长度的点集（T）
初始所有点均属于 T 且所有点的最短路距离均为＋∞，将源点（出发点）放入 S，并将最短路数组设为 $0$。
不断执行以下操作：
- 从 T 集合中，选取一个最短路长度最小的节点，移到 S 中。
- 对于刚加入 S 的节点，松弛所有出边。
直到 T 集合为空，算法结束。
时间复杂度瓶颈为选取一个最短路长度最小的节点：
- 暴力选取：算法时间复杂度为：$O(n^2+m)$。
- 二叉堆选取：松弛成功时要将节点插入二叉堆（若已经加入需要删除），同时每个点也会被取出 $1$ 次，时间复杂度：$O(n\log n+m\log n)$。
- 优先队列选取：同二叉堆，但优先队列不能删除元素，所以松弛成功插入时，时间复杂度单次为 $O(\log m)$，总时间复杂度：$O(n\log m+m\log m)$。
- 其它动态维护最值的方式。
虽然算法原理角度不同，但是算法流程和优先队列 BFS 在图上的实现是一致的，所以证明略。
关于负权图中失效的问题在优先队列 BFS 中也有解释，不赘述。
Bellman-Ford：
一种基于松弛操作的用于求单源最短路的算法（可以求有负权的图的最短路问题）。
过程：
初始化源点最短路数组为 $0$，不断重复地对所有边进行松弛操作。
时间复杂度：$O(nm)$。
原理：
在最短路存在的情况下，每一轮松弛操作（因为无法获知最短路是哪一条，所以需要对所有边松弛。同时，最短路也不会只有一条），会使得最短路的节点数$+1$。
而图中最短路最多经过 $n$ 个点，所以进行 $n-1$ 轮松弛即可找到最短路。
判负环：
若存在负环，则可以一直松弛，所以若是 Bellman-Ford 在第 $n$ 轮松弛中还有点被更新，即有负环。
特殊性：
根据 Bellman-Ford 的原理，容易发现，在第 $i$ 轮松弛操作时，求出的最短路数组即为“经过 $i$ 条边的最短路”。
SPFA：
Bellman-Ford 队列优化。
虽然 SPFA 通常指队列优化，但是本身是对松弛操作次数的优化，所以不一定使用队列，也存在 SPFA-DFS 实现的说法。
Bellman-Ford 将所有边松弛了 $n-1$ 轮，而在实际问题中，最短路不一定经过 $n$ 个点，也不是所有边都能有效松弛。所以考虑将所有点放入队列中，若是一个点已经不能松弛任何点了，那在后续的过程中就不再考虑了。
实际上，SPFA 就可以视作普通 BFS 求最短路。
时间复杂度：$O(m)\sim O(nm)$。
SPFA 在最坏情况下和 Bellman-Ford 一致。
朴素的 SPFA 使用菊花即可卡成和 Bellman-Ford 一致。
尽管 SPFA 存在各式形形色色的优化，但是都是可以在特殊情况下得到较劣的时间复杂度，甚至在部分情况下会出现指数级别的时间复杂度（SPFA-DFS 在无负环时判负环）。
一般而言，除非必要（负权图求最短路），不使用 SPFA。
Floyd：
一种基于动态规划的全源最短路算法。
设 dp$[k][x][y]$ 表示从 $x$ 到 $y$ 只经过 $1-k$ 号点的最短路。
$(k,x,y)\leftarrow(k-1,x,k)+(k-1,k,y)$。
先枚举 $k$，再枚举点 $x,y$。
时间复杂度：$O(n^3)$。
特殊性：
传递闭包：
可以使用 Floyd 求传递闭包，即：图的完整连通情况。同时因为连通性只含 0/1，使用 bitset 可以优化至 $O(\frac{n^3}{\omega})$。
无向正权图最小环：
dp$[z-1][x][y]$ 和 $(x,z),(z,y)$ 构成一个环。
矩阵快速幂：
Floyd dp$[k][x][y]$ 只与 dp$[k-1][x][y]$ 有关，所以可以采用滚动数组优化，同时类似 01 背包，dp$[k][x][y]$ 可以继承自 dp$[k-1][x][y]$。所以可以直接去掉第一维，而去掉第一维后，对于 DP 式子而言，可以抽象地视作一个矩阵乘法的过程。$\min$ 视作 $\sum$，$+$ 视作 $\times$。
时间复杂度优化至：$O(n^2\log n)$。但通常没必要。
Johnson 全源最短路：
最短路问题上，实现目的与 Floyd 一致。
时间复杂度：$O(nm\log m)$。
若是正权图，分别以 $n$ 个点作为源点求最短路即可；若是负权图，
有向无环图的最短路：
DP 问题。
边权为 1 的最短路：
BFS。
略。
边权为 0/1 的最短路：
01 BFS。
略。