最短路相关 ​

floyd ​

适用范围 ​

稠密图全源最短路。

算法原理 ​

常见的 floyd 是实时维护一个点集 $V$，当前 $dis[i][j]$ 表示从 $i$ 到 $j$ 只能中途经过 $V$ 中点的最短路。注意，这里的“中途”不含起点和终点（这是因为 朴素的 floyd 初始 $f[i][j]$ 表示邻接矩阵）。当然，可以改成每次路径全程不经过某些点，这只需要特判起点和终点即可。

正确性证明 ​

每次新增一个点，$i,j$ 之间的最短路要么经过，要么不经过。

• 不经过就是原来的 $dis$。
• 经过的话，如果图没有负环，必然经过恰一次，就是 $dis[i][k]+dis[k][j]$。 注意这里是滚动实现，因为没有负环时，经过同一个点两次必然不优。

判负环 ​

必然有一个点经过了两次，做两次 floyd，在第二次看能不能再松弛即可。

扩展 ​

结合线段树分治实现稠密图加点删点全源最短路（边的问题类似）。

dijkstra ​

适用范围 ​

非负权单源最短路。

原理 ​

简单贪心，略。

扩展：模拟 dij ​

dij 的过程非常简单，核心就两步：

• 找到最小点。
• 用当前点松弛所有相连点。

模拟的难点在于松弛部分，通常可以用 DS 实现。经典的：处理区间连边。

bellman - ford ​

正确性证明 ​

没有负环的时候，最短路长度 $\leq n$。

spfa ​

复杂度证明 ​

每个点入队必然因为某条新边导致的最短路，最多入队 $m$ 次。

判负环 ​

建立超级源点，连向每一个点，跑 spfa（保证连通性），同时记录最短路点数，超过 $n$ 就有负环。

优化 ​

• 直接优化（正式比赛不要往这方面想）：比较常用的是 SLF 优化。
• 去掉负权边跑 dij（常用）：
  • 重新设计建图。
  • 结合图的特性，合理赋势能。

k - bfs ​

适用范围 ​

边权非负且值域可以接受。

本质 ​

模拟 dij，通过让每个队列内部不降，保证取到最小值。

复杂度 ​

$O(nv + m)$，特别的有 01bfs。

差分约束问题 ​

• 处理不等关系：直接建边。
• 相等关系：建双向边。
• 和特殊值的不等关系：取虚点建边。

johnson ​

利用差分约束实现一般图的赋势能。

最短路树 ​

以下都是有向任意边权图。

定义 ​

• 最短路 DAG：满足 $dis[v]=dis[u]+w(u,v)$ 的边组成的图。
• 最短路树：最短路 DAG 的生成树，注意，这是有向树。

性质 ​

• （核心）非树边满足三角形不等式。
• 任何一条从 $st$ 出发到 $ed$ 的简单路径和合法的非树边序列一一对应。合法：序列中的任何非树边前驱能只走树边到该非树边。
• 路径权值和非树边序列权值的对应关系：
  • 将非树边的权值重定义为 $dis[v]+w(u,v)-dis[u]$。
  • 路径的长度就是非树边权值和加上 $st,ed$ 之间的最短路长度。

k 短路 ​

• 不要求简单路径：在 dij 过程中第 $k$ 次取出的 $x$ 点 $dis$ 就是 $k$ 短路。
• 简单路径：结合最短路树和调整法实现。

同余最短路 ​

适用范围 ​

存在性完全背包问题。

原理 ​

任取一个基准物品，记其体积为 $mod$。那么，对于 $0\leq i\lt mod$，$dis[i]$ 表示到达 $j\times mod + i$ 的最小的 $j\times mod + i$。对于体积为 $v$ 的物品，其松弛形如 $chkmi(dis[(i + v)%mod],dis[i]+v)$。判定一个体积 $v$ 是否可以表示出来，可以直接看 $dis[v%mod]$ 和 $v$ 的大小关系。

优化思考 ​

直接实现是最短路，但是，这是否可以直接 DP 去掉 $\log$ 呢？观察松弛进行的条件，假设从 $st$ 开始，持续松弛成功，过程形如环上跳。而这个跳肯定不会一直成功到 $st$（因为一开始就是用 $dis[st]$ 松弛的）。所以，可以枚举 $st$，模拟跳的过程，转两圈，保证每个环上点都松弛到位。核心：不会经过同一个状态。

删边最短路 ​

处理 无向正权图 的删边后的固定起终点最短路。下面求 1 到 $n$ 的删边最短路，建出两个最短路树做，懒得写了，太少用了。

次短路的扩展应用：维护多个最值处理限制 ​

适用背景 ​

处理带限制的最短路（DP 转移）。限制可以被刻画成：解的特征值恰不等于给定集合中的任何一个，其中，特征值需要自己设计。

适用条件 ​

对于同一个点（状态），不合法的边（转移）的数量是可以接受的。

经典例子 ​

• 最短路相邻不能经过相同的点。
• 最短路源点不同。

处理办法 ​

• 维护(最多不合法数量 + 1)个最值，要求最值的特征值两两不同。
• 每次松弛（转移），分类讨论：
  • 如果最值集合中没有当前特征值：尝试用当前最值替换集合中的最劣解。
  • 如果最值集合中有当前特征值：直接更新对应最值。
• 如果是 DP，直接朴素维护或平衡树维护。
• 如果是 dij，每个集合中的最值对应一个点，每次松弛最多更新一个点的 $dis$，及时将其放入队列。

例题 ​

最短路，但是每个点有点权，要求路径的任何一个前缀的点权异或和不为 0。

solution ​

直接做就可以了，此题当然可以加强，但我懒得。