最短路算法拓展技巧
Floyd 传递闭包
有时候我们需要维护一些具有传递性的关系，如相等，连通等。
初始条件往往是给定几组关系，要把所有的关系求出来。
可以把 Floyd 算法做一些调整：
$$dis_{i,j}=dis_{i,j}~|~(dis_{i,k}~\&~dis_{k,j})
$$
时间复杂度还是 $\Theta(n ^ 3)$，但由于位运算的特殊性，有些时候可以使用 bitset 优化到 $\Theta\left(\frac{n ^ 3}{\omega}\right)$。
Johnson 重赋权
对于多源最短路，如果我们枚举一个点然后跑堆优化的 Dijkstra，那么复杂度是 $\Theta(nm \log n)$ 的，在图比较稀疏的情况下，这个复杂度要优于 Floyd 算法的 $\Theta(n ^ 3)$。
但是 Dijkstra 算法要求所有边权均非负，于是就有了重赋权的技巧。
具体来说，我们新建一个 $0$ 号点，并且从这个点出发向所有点连一条边权为 $0$ 的边，然后跑单源最短路(SPFA 或者 Bellman-Ford)。设距离数组为 $h$， 接下来对于每条边 $(u, v)$， 令
$$w^{\prime}(u, v)=w(u, v)+h(u)-h(v)
$$
这样所有的边权都变成非负的，我们就可以跑 Dijkstra 算法了。
接下来证明这样做为什么是对的：
首先由于 $h(v) \leqslant h(u)+w(u, v),$ 所以新图的边权一定非负。
设新图上的最短路径为 $d^{\prime}$，原图上的最短路径为 $d$。
$$\begin{aligned}d^{\prime}(u, v) &= \min _{a_{1}, a_{2}, \ldots, a_{k}} w^{\prime}\left(u, a_{1}\right)+w^{\prime}\left(a_{1}, a_{2}\right)+\cdots+w^{\prime}\left(a_{k}, v\right) \\\\
&= \min _{a_{1}, a_{2}, \ldots, a_{k}} w\left(u, a_{1}\right)+\left(h(u)-h\left(a_{1}\right)\right)+w\left(a_{1}, a_{2}\right)+\left(h\left(a_{2}\right)-h\left(a_{1}\right)\right)+\cdots+w\left(a_{k}, v\right)+\left(h(v)-h\left(a_{k}\right)\right) \\\\
&= h(u)-h(v)+\min _{a_{1}, a_{2}, \ldots, a_{k}} w\left(u, a_{1}\right)+\cdots+w\left(a_{k}, v\right) \\\\
&= h(u)-h(v)+d(u, v)\end{aligned}
$$
这个证明用到了势能分析的思想，如果想进一步了解话可以参考本站《「杂项」复杂度分析》一文。
最短路图
所谓最短路图，就是在求完从 $S$ 出发的单源最短路之后，只保留最短路上的边形成的有向图。
只需要在求的过程中维护一个 $pre_u$ 数组表示点 $u$ 的前驱即可。
很多最短路的变种都需要用这个算法，有时候考虑最短路图也有利于发现一些隐藏的性质。
经典例题
[LG1266] 速度限制
记 $dis_{i,j}$ 表示当前已经到 $i$，上一个点是 $j$ 的时间最短路。
本质上是个分层图最短路，直接跑 Dijkstra 就好了。
时间复杂度 $\Theta(nm\log n)$。
[ICPC-BJ2006] 狼抓兔子
首先有定义 ：
- 平面图是指的存在某种方式使得图上所有边平铺在平面上无交。
- 对偶图是指的将平面图上的每个区域看作一个点，两点连边当且仅当两区域相邻，边权为将两区域分隔开的边的权值。
有定理 ：
平面图两点间最小割等于对偶图两点间最短路。
于是在这道题中我们就可以将每个三角形区域看作一个点，相邻区域连边后跑从左下角到右上角的最短路。
时间复杂度 $\Theta(n^2\log n)$。
[GXOI/GZOI2019] 旅行者
我们发现可以对 $k$ 个点二进制分组，每次将 $k$ 个点分成两个集合 $S_1$ 和 $S_2$，建一个源点 $s$ 向所有 $S_1$ 中的结点连长度为 $0$ 的边，建一个汇点 $t$ 从所有 $S_2$ 中的结点开始向它连长度为 $0$，的边，求从 $s$ 到 $t$ 的最短路。
可以发现，若答案为两点 $x$ 和 $y$ 之间的最短路，那么一定有 $x\not= y$，这意味着它们至少在某一次二进制分组中被分到了不同的集合，所以这样一定可以找到两点间的最短路。
时间复杂度 $\Theta(Tn\log n\log k)$。