最短路算法拓展技巧
Floyd 传递闭包
有时候我们需要维护一些具有传递性的关系，如相等，连通等。
初始条件往往是给定几组关系，要把所有的关系求出来。
可以把 Floyd 算法做一些调整：
\[ dis_{i,j}=dis_{i,j}~|~(dis_{i,k}~\mathbin{\&}~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)\)。
