最短路算法总结，建图，最长路，负环，差分约束，最短路径树/图，最短路计数。

最短路及其应用

最短路算法

bfs

一般用于不带权的图，由于不带权，所以只需要数边数，这个时候就可以直接使用 bfs 去得到最短路长度以及最短路。复杂度 $O(n + m)$

有时候可能会遇到多源无权图最短路，这个时候可以建立虚拟源点指向各个实际源点，然后做 bfs 。

bfs 求最短路的特点是每个点只入队和出队一次，并且是按照拓扑序做的最短路，把所有当前最短长度的都算出来了才轮到下一层。

dijkstra

求单源最短路，贪心的思路，每次找还没找到最短路的点中当前离源点最近的那个，将其标记为已经找到最短路，然后从这个点往外扩展一圈，使用三角不等式更新距离。朴素做法复杂度 $O(n^2)$， 堆优化复杂度 $O((m + n)\log n)$

由于基于贪心思路，所以需要没有负边权，才能保证已经找到最短路的点的距离不会再被更新。

dijkstra 算法每个点第一次出队的顺序是满足长度的拓扑序的。

floyd

求全源最短路，动态规划的思路，考虑 dp[k][i][j] 为 i 到 j 的只允许经过编号不超过 k 的中间点的最短路，可以压掉第一维，然后使用三重循环转移。复杂度 $O(n^3)$ 。

注意到这个基于动态规划的思路，所以只要最短路存在（没有负环），那么就可以得到正确结果。

bellman-ford

求单源最短路的另一种算法，完全基于三角不等式。本算法需要遍历所有的边，遍历到每条边时，假设这条边是 (u, v, w)，则考虑是否能通过 d[u] > d[v] + w 来更新最短路，能更新则更新。直到某一轮没有任何一个点的最短路被更新，则停止。可以证明，如果没有负环，每个点至多被更新 n - 1轮 ，所以如果某个点在第 n 轮还被更新，可以直接判定存在负环。复杂度 $O(nm)$ 。想求以哪个点为源的最短路，就把哪个点的初始值设置成0，其他的设置成无穷大即可。

bellman-ford 算法可以处理负边权，可以判断是否有负环。

bellman-ford 系列的最短路在求解时没有拓扑序，会存在已经用来更新别的点的点又被别的点更新的情况。

spfa

全称“队列优化的 bellman-ford 算法”，对随机情况优化比较好，但是最坏的复杂度不变。队列优化的思路是，如果某个点在这一轮没有被更新，那么以后也不会被更新，所以我们可以使用队列去存储本轮被更新的点。对于一个点来说，其在一轮中可能被多次更新，但是只入队一次，我们看其在几轮中被更新意味着看其入队了多少次，所以每入队一次我们就统计一次次数。

spfa 可以处理负边权，可以判断是否有负环。

应用

建图

虚拟源点

虚拟源点主要可以解决多个起点多个终点的问题。所以如果发现很裸的建图会出现因为起点和终点而不好处理的问题，则可以考虑这么干。

反图

建立反图可以解决终点确定，但是起点不确定的问题。

二分图

TODO

最长路

负环

差分约束

对于一系列 $x_i \leq x_j + c_k$ 的不等式，考虑连接一条从 $x_j$ 到 $x_i$，长度为 $c_k$ 的有向边，然后求一次最短路，就必然有 $d[i] \leq d[j] + c_k$，所以距离数组的值就是这组不等式的一个解。

如果不等式组是 $x_i \geq x_j + c_k$，那么可以做最长路。

如果不等式组中存在 $x_i \leq c$ 这种不等式，可以建立超级源点 $x_0$，并规定 $d[0] = 0$，那么从 $x_0$ 到 $x_i$ 连一条边就可以了。

对于严格不等式 $x_i < x_j + c_k$ ，整数范围内可以转化为 $x_i\leq x_j + c_k - 1$

在做最短路的时候，要谨慎选择源点。由于每条边就是一个不等式，所以我们一定要选择一个能够遍历到所有边的源点。

如果是求最短路，那么存在负环等价于不等式组存在矛盾；如果是求最长路，那么存在正环等价于不等式组存在矛盾。判断环的时候可以使用 spfa，过不了可以试试栈优化。

如果我们不满足于可行解，想找一组“最优解”，比如每个变量能够取到的最小值或者最大值，则对应着应该求最长路或者最短路。以求最大值为例子，我们要让所有能走到 $x_i$ 构成的链表示的不等式链都成立，可以得到 $x_i \leq C_1, x_1 \leq C_2...$ 一系列上界，最大值就是这些上界的 $min$ 。因为做最短路的时候才是 $d[i] \leq d[j] + c_k$ ，所以求最短路得到的是最大值。

最短路径树

最短路径树，是一个图的生成树，这个树以某个点为根，然后这个点在原图中到其他点的最短路径的长度就是这个树上的从根到这个儿子的唯一路径的长度。

最短路径树的树边的判断：先预处理一遍最短路，然后从根开始做 dfs，只要有 d[j] = d[i] + w，就说明是一条树边。为了防止重边干扰，做 dfs 的时候要及时使用判重数组。

3628. 边的删减 - AcWing题库 是一个比较容易发现考察的是最短路径树的问题，可以用来练习。

我在vp第二次周赛的时候遇到的这个题目，但是我还不会这个东西，所以我在网上搜到了这个东西的求法。后来在听讲解的时候发现这个是提高课里的内容，可惜我提高课的图论进度大概不到50%，麻了。

如果把所有点的最短路前驱都加进来，那么虽然得到的不是最短路径树，但是得到的东西也不错，如果没有 0 环，那么得到的就是一个拓扑图。

最短路计数

这个事情就是在最短路径图上做的。

分层图最短路

拆点。

预处理最短路

头尾一起做最短路，然后就可以对中间部分的图进行一些操作（比如加边删边），从而快速求出新的最短路。