https://csacademy.com/app/graph_editor/
https://riverhamster.gitee.io/app/graph_editor/
注：时间复杂度分析中，假设 \(n \le m \le n ^ 2\)
最短路本质上是一种 DP
阶段：点
状态：拆点
决策：边
最优子结构：最短路的任何子路径都一定是最短路
无后效性：正权图中一定可以找到一种无后效性的枚举顺序（Dijkstra）
重复子问题：\(dis_i\) 表示所有以 \(i\) 为结尾的所有路径的长度的最小值
存图
本来不打算写的，但是发现 vector + O2 跑得比链前快之后真的绷不住了
主要原因是 vector 比链前慢的地方是在建图是需要动态分配内存，但是存完图后每个点连出的边就储存在一段连续的内存中，利用 cache 机制大量访问会比较快
但是链前真的很酷。
Dijkstra
- 朴素版
本质上是通过贪心的方式找到一种使得 DP 没有后效性的转移顺序
将所有点分为 \(S\) 和 \(T\) 两个集合，\(S\) 表示最短路确定且不会再更改，\(T\) 表示最短路未确定，最开始所有点都在 \(S\) 中。每次从 \(T\) 找出最短路最小的点，用它更新其他点的最短路，并放进 \(S\) 集合
因为所有边的边权都是正数，所以每次找出的最小的点肯定不会被其他 \(T\) 集合中的点再更新最短路
也就是说，每个点一定是以最短路长度从小到大的顺序被放入 \(S\) 集合的，前面一定不会被后面影响。这也是一个 DAG 的拓扑序
- 堆优化 / 线段树优化
每次找出 \(T\) 集合中最短路最小的点可以用堆优化，STL 优先队列 \(O(m \times \log m)\)，手写二叉堆 \(O(m \times \log n)\)，斐波那契堆 \(O(n \times \log n + m)\)
不会手写堆可以线段树，也是 \(O(m \times \log n)\)。但线段树实际上一般比 STL 更慢（NKOJ 不加快读甚至会 TLE），因为一定会把 \(O(m \times \log n)\) 跑满，但是一般不会有毒瘤出题人把优先队列的 \(\log m\) 卡满 而且 log m 和 log n 本来就差不了多少，线段树常数还大。这里给出线段树的参考代码，但是在 NKOJ（和其他任何 OJ）上不建议使用。
#include <cstdio>
#include <algorithm>
#include <cctype>
namespace fastio
{
const int MAXBUF = 1 << 20;
char buf[MAXBUF], *p1 = buf, *p2 = buf;
inline char getc() { return (p1 == p2) && (p2 = (p1 = buf) + fread(buf, 1, MAXBUF, stdin)), p1 == p2 ? EOF : *p1++; }
} // namespace fastio
using fastio::getc;
template <class _Tp>
inline _Tp& read(_Tp& x)
{
bool sign = 0;
char ch = getc();
for (; !isdigit(ch); ch = getc()) sign |= (ch == '-');
for (x = 0; isdigit(ch); ch = getc()) x = x * 10 + (ch ^ 48);
return sign ? (x = -x) : x;
}
const int maxn = 400000 + 10, maxm = 2000000 + 10;
struct graph
{
int cnt;
int st[maxm], to[maxm], last[maxn], next[maxm];
long long w[maxm];
graph() { cnt = 0; }
void add(int x, int y, long long z)
{
cnt++;
st[cnt] = x, to[cnt] = y, w[cnt] = z;
next[cnt] = last[x], last[x] = cnt;
}
}
g;
struct segmentTree
{
long long a[maxn];
struct node { int l, r, pos; } T[maxn << 2];
void build(int p, int l, int r)
{
T[p].l = l, T[p].r = r, T[p].pos = l;
if (l == r) a[l] = 1LL << 60;
else build(p << 1, l, (l + r) >> 1), build((p << 1) | 1, ((l + r) >> 1) + 1, r);
}
int modify(int p, int k, long long d)
{
if (T[p].r < k || T[p].l > k) return T[p].pos;
else if (T[p].l == k && T[p].r == k) return a[k] = d, T[p].pos = k;
else return T[p].pos = a[modify(p << 1, k, d)] <= a[modify((p << 1) | 1, k, d)] ? T[p << 1].pos : T[(p << 1) | 1].pos;
}
}
T;
long long dis[maxn];
long long dijk(int st, int ed, int n)
{
T.build(1, 1, n);
T.modify(1, st, 0);
for (int i = 1; i <= n; i++) dis[i] = 1LL << 60;
dis[st] = 0;
while (n--)
{
int u = T.T[1].pos;
if (T.a[u] >= 1LL << 60) break;
if (u == ed) return dis[u];
for (int j = g.last[u]; j != 0; j = g.next[j])
{
int v = g.to[j]; long long w = g.w[j];
if (dis[v] > dis[u] + w) T.modify(1, v, T.a[u] + w), dis[v] = dis[u] + w;
}
T.modify(1, u, 1LL << 60);
}
return -1;
}
int main()
{
int n, m;
read(n), read(m);
for (int i = 1; i <= m; i++)
{
int x, y;
long long z;
read(x), read(y), read(z);
g.add(x, y, z);
}
int st, ed;
read(st), read(ed);
printf("%lld", dijk(st, ed, n));
return 0;
}
Bellman-Ford
- 朴素版
进行 \(n - 1\) 次遍历每个边的松弛操作
因为在无负权回路图中最短路不会经过重复点，长度最多为 \(n - 1\)，所以在第 \(i\) 次松弛操作中一定能松弛到最终答案的第 \(i\) 条边
时间复杂度 \(O(n \times m)\)（也可以是 \(O(\text{边数最长的最短路长度} \times m)\)）
- 队列优化（SPFA）
显然只有最短路变化的点才可能更新其他点，所以每次可以把变化的点存下来，再用这些点去更新其他点。时间复杂度为边数乘每个点的平均入队次数 \(O(k \times m)\)，随机图中 \(k < 5\)，构造图可以卡到 \(O(n \times m)\)。有一些神奇的优化，但是肯定可以被卡。在一些特殊图中还是有一定的作用，但不多
- 判负权回路
如果进行 \(n - 1\) 次松弛操作后仍然可以松弛，那么图中存在负环。SPFA 中可以记录每个点的入队次数，超过 \(n\) 次说明存在负环。但是只能判可以从起点到达的负环
Floyd-Warshall
- 朴素版
设 \(f_{k,i,j}\) 表示 \(i\) 到 \(j\) 只经过前 \(k\) 个点的最短路
则 \(f_{k,i,j} = \min(f_{k-1,i,j}, f_{k-1,i,k} + f_{k-1,k,j} )\)
- 滚动数组优化
滚动第一维，得到 \(f_{i,j} = \min(f_{i,k} + f_{k,j} )\)
因为 \(k\) 并不在 \(i\) 到 \(k\) 的最短路中，所以 \(f_{i,k}\) 在此时表示 \(f_{k-1,i,k}\) 还是 \(f_{k,i,j}\) 都不会有影响，可以直接压缩。\(f_{k,j}\) 同理
循环顺序保持不变，还是 \(k,i,j\)
其实三个循环顺序可以随意交换，在外面再套一个 \(3\) 次的循环即可
没用的知识又增加了
- 判负权回路
如果 \(f_{i,i} < 0\)，说明点 \(i\) 在一个负权回路中
- 传递闭包
设 \(f_{i,j} = 1\) 表示 \(i\) 与 \(j\) 连通，反之不连通，然后使用 Floyd 的三层循环进行求解
可以用 bitset 优化，时间复杂度 \(O(\frac{n ^ 3}{w})\)
BFS
你就说能不能求最短路吧
边权为 \(1\) 用队列，边权为 \(0\) 或 \(1\) 用双端队列，如果经过一条边权为 \(0\) 的边更新一个点放到队头，边权为 \(1\) 放到队尾，第一次取出一个点时它的最短路就一定是已经确定的。时间复杂度 \(O(m)\)
对于边权无限制，有两种解决办法。一是允许节点被多次更新 然后就变成 SPFA 了呢，二是改成优先队列 然后就变成 Dijkstra 了呢
最小环
https://oi-wiki.org/graph/min-cycle/
https://www.luogu.com.cn/problem/P6175
第一种方法是枚举图中每一条边，再用 Dijkstra 计算这条边的两个端点在不经过这条边本身的最短路，最终答案即为 \(dis_{v,u} + w_{u,v}\)。时间复杂度为 \(O(m ^ 2 \times \log n)\)
第二种方法需要用到 Floyd 中的性质。因为 \(f_{k,i,j}\) 表示 \(i\) 到 \(j\) 只经过前 \(k\) 个点的最短路，
连通性
并查集。
最短路相关计数
如果对每一条边都枚举最短路可能经过它的起点和终点，时间复杂度太高。考虑对一个点求出单源最短路后枚举对每一条边答案的贡献（控制变量法——前物理科代表 \(a^6q^6\)）
因为最短路中不会出现环，且最短路的前缀一定是最短路，所以所有可以被作为最短路上的边（\(dis_u + w = dis_v\)）一定构成了一个有向无环图，这个 DAG 上的任何一条路径都是最短路，可以在 Dijkstra 过程中求出拓扑序，然后按拓扑序进行计数
#include <cstdio>
#include <algorithm>
const int maxn = 1500 + 10, maxm = 5000 + 10;
const long long inf = 1LL << 60;
struct graph
{
int cnt;
int st[maxm], to[maxm], last[maxn], next[maxm];
long long w[maxm];
graph() { cnt = 0; }
void add(int x, int y, long long z)
{
cnt++;
st[cnt] = x, to[cnt] = y, w[cnt] = z;
next[cnt] = last[x], last[x] = cnt;
}
}
g, gt;
struct segmentTree
{
long long a[maxn];
struct node { int l, r, pos; } T[maxn << 2];
void build(int p, int l, int r)
{
T[p].l = l, T[p].r = r, T[p].pos = l;
if (l == r) a[l] = inf;
else build(p << 1, l, (l + r) >> 1), build((p << 1) | 1, ((l + r) >> 1) + 1, r);
}
int modify(int p, int k, long long d)
{
if (T[p].r < k || T[p].l > k) return T[p].pos;
else if (T[p].l == k && T[p].r == k) return a[k] = d, T[p].pos = k;
else return T[p].pos = a[modify(p << 1, k, d)] <= a[modify((p << 1) | 1, k, d)] ? T[p << 1].pos : T[(p << 1) | 1].pos;
}
}
T;
long long dis[maxn];
int cnt = 0;
int ord[maxn];
void dijk(int st, int n)
{
cnt = 0;
T.build(1, 1, n);
T.modify(1, st, 0);
for (int i = 1; i <= n; i++) dis[i] = inf;
dis[st] = 0;
while (n--)
{
int u = T.T[1].pos;
if (T.a[u] >= inf) break;
ord[++cnt] = u;
for (int j = g.last[u]; j != 0; j = g.next[j])
{
int v = g.to[j]; long long w = g.w[j];
if (dis[v] > dis[u] + w) T.modify(1, v, T.a[u] + w), dis[v] = dis[u] + w;
}
T.modify(1, u, inf);
}
return;
}
const long long mod = 1e9 + 7;
long long ans[maxm];
long long in[maxn], out[maxn];
int main()
{
int n, m;
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++)
{
int x, y;
long long z;
scanf("%d %d %lld", &x, &y, &z);
g.add(x, y, z);
gt.add(y, x, z);
}
for (int i = 1; i <= n; i++)
{
dijk(i, n);
for (int j = 1; j <= n; j++) in[j] = out[j] = 0;
in[i] = 1;
for (int k = 1; k <= cnt; k++)
{
int u = ord[k];
for (int j = gt.last[u]; j != 0; j = gt.next[j])
{
int v = gt.to[j];
long long w = gt.w[j];
if (dis[v] + w == dis[u]) in[u] = (in[v] + in[u]) % mod;
}
}
for (int k = cnt; k >= 1; k--)
{
int u = ord[k];
out[u] = 1;
for (int j = g.last[u]; j != 0; j = g.next[j])
{
int v = g.to[j];
long long w = g.w[j];
if (dis[u] + w == dis[v]) out[u] = (out[u] + out[v]) % mod;
}
}
for (int j = 1; j <= m; j++)
{
int u = g.st[j], v = g.to[j];
if (dis[u] + g.w[j] == dis[v]) ans[j] = (ans[j] + in[u] * out[v]) % mod;
}
}
for (int i = 1; i <= m; i++) printf("%lld\n", ans[i]);
return 0;
}
虚点
https://www.cnblogs.com/SillyTieT/p/11545966.html
分层图最短路 / 多维最短路 / 拆点
其实就是 DP
线段树优化建图
咕咕咕
P8817 [CSP-S 2022] 假期计划
看到范围 \(n \le 2500\) 不难想到可以枚举其中两个点。既然都直接枚举了，那也没必要枚举 A 和 D 这种快确定的点