单源最短路径
贡献者： 有机物
单源最短路径问题，为给定一张有向图 $G = (V, E)$，$V$ 是点集，$E$ 是边集，$|V|= n$，$|E| = m$，求给定的源点（起点）$s \in V$ 到每个结点 $v \in V$ 的最短路径。$(x, y, w)$ 表示有一条从结点 $x$ 指向结点 $y$ 的有向边，边权为 $w$。
1. Dijkstra 算法
dist[i] 表示从起点 $s$ 到结点 $i$ 的实际最短路径的长度（这条路径的权值之和）。
$\delta(u)$ 表示从起点 $s$ 到结点 $u$ 的估计最短路径长度。任意时刻都存在 $dist[u] \leq \delta(u)$。 Dijkstra 算法是一种求解没有负权边的图中的单源最短路问题。将所有结点划分为两个集合，$S$ 集合存储当前已经确定了最短路的结点，$T$ 集合存储当前还未确定最短路的结点。
具体做法是：
- 初始化所有点的
dist距离为正无穷，起点的距离为 $0$（dist[S] = 0）。 - 每次从 $T$ 集合中选出一条
dist值最小的结点 $t$，并把 $t$ 结点加入 $S$ 集合中。 - 用 $t$ 更新其他结点。
- 重复 $2 \sim 3$ 步骤，直到所有点都被加入 $S$ 集合。
朴素 Dijkstra 算法的时间复杂度为 $\mathcal{O}(n \times m)$，使用二叉堆可以使操作 $2$ 的时间复杂度从 $\mathcal{O}(n \times m)$ 的时间复杂度优化到 $\mathcal{O}(\log_2 n)$。每更新一条边 $(x, y)$，就把 $y$ 这个结点和 dist[y] 值插入到二叉堆中。每次找最小值直接取堆顶即可。每次取堆顶时判断堆顶是不是已经被访问过了，如果被访问过了，直接忽略这次操作，否则会重复更新，导致影响时间复杂度。所以堆优化版 Dijkstra 的时间复杂度为 $\mathcal{O}(m \log_2 n)$。
Dijkstra 算法正确性证明：
1. 参考算法导论中的反证法
要证明在算法结束时，每个点的实际最短距离等于估计最短距离，即证明的是对于每个结点 $u \in V$，当结点 $u$ 第一次加入到 $S$ 集合时，$dist[u] =\delta(u)$，也就是 dist[u] 必然满足已经是起点到 $u$ 的最短距离。
初始化：$S = \varnothing$，方程显然成立，得证。
接下来使用反证法证明此结论，假设结点 $u$ 是第一次加入 $S$ 集合时使得 $dist[u] \neq \delta(u)$，因为 $s$ 结点是第一次加入 $S$ 集合中的结点，所以有 $dist[s] = \delta(s) = 0$，因为 $s$ 结点是第一个加入 $S$ 结点中的结点，所以将 $u$ 结点加入 $S$ 集合之前，必定有 $S \neq \varnothing$。此时一定有一条从 $s$ 结点到 $u$ 结点的路径，否则 $dist[u] = \delta(u) = +\infty$，而这与假设矛盾，所以一定存在一条路径从结点 $s$ 到结点 $u$。
所以这条路径上一定存在一条最短从结点 $s$ 到结点 $u$ 的最短路径 $p$。 将 $p$ 分解为：$s \thicksim x \thicksim y \thicksim u$，其中 $y$ 为第一个属于 $T$ 集合中的点，$x$ 为 $y$ 的前驱结点。有可能存在 $s = x$ 或 $y = u$ 的情况。
因为结点 $u$ 是第一次加入 $S$ 集合时不满足 $dist[u] \neq \delta(u)$ 的结点，所以在之前所以的结点都满足实际最短路径等于估计最短路径，所以在将 $x$ 结点加入到 $S$ 集合时，满足 $dist[x] = \delta(x)$。此时 $x$ 结点会更新其他结点，所以在将 $u$ 加入到 $S$ 集合时，$dist[y] = \delta(y)$。
因为结点 $y$ 是结点 $u$ 的前面的一个结点，所以存在 $\delta(y) \leq \delta(u)$。所以 $dist[y] = \delta(y) \leq \delta(u) \leq dist[u]$。又因为结点 $u$ 是算法在 $T$ 集合中选择的第一个点，所以有 dist[u] <= dist[y]。所以上面的不等式其实都为等式，所以 $\delta(u) = dist[u]$ 成立，这与假设矛盾，所以证明得证。
2. 使用数学归纳法证明
证明在第 $k$ 步算法选择的不在 $S$ 集合中距离 $S$ 集合最近的点，它在被加入 $S$ 集合时，它的路径就是最短路径。
首先当 $k = 1$ 时，$S$ 集合中只有源点 $s$，它的最短路径已经被确定，就是 $0$。
假设对 $k$ 成立，那么对第 $k + 1$ 步也成立。
令 $d_i = dist[i]$，$w$ 为边权。
第 $k$ 步算法选择的点为 $u$，它的最短路径已经被确定，并且加入到了 $S$ 集合中。考虑第 $k + 1$ 步算法选择了 $u \to v$ 这条边的 $v$ 结点。若存在另一条路径 $s \to y \to v$，即证：$d_v \leq d_y + w(y \to v)$。
反证法：假设算法第 $k + 1$ 选择了 $y$，那么有：$d_v > d_y + w(y \to v)$，看看有没有什么矛盾发生。因为有 $d_v > d_y + w(y \to v)$，所以不难看出：$d_v > d_y$，因为第 $k$ 步算法选择了 $u$ 这个点，所以在图上可以看出 $d_y \geq d_u$，因为：$d_v > d_y$，并且 $d_v = d_u + w(u \to v)$，所以有 $d_u + w(u \to v) > d_y$，又因为 $d_y \geq d_u$，所以 $d_u + w(u \to v) > d_u$。可以从图中看出，$d_u$ 无论如何也不可能严格大于 $d_v$，所以假设不成立，所以 $d_v \leq d_y + w(y \to v)$ 式成立。
证毕。
C++ 代码：
朴素版 Dijkstra
const int N = 1e5 + 10, M = 510, INF = 0x3f3f3f3f;
int n, m, dist[N], st[N], g[M][M]; // st 为 true 表示在 S 集合，反之不在
int dijkstra()
{
memset(dist, 0x3f, sizeof dist); // 初始化距离
dist[1] = 0;
for (int i = 0; i < n - 1; i ++ ) // 迭代 n - 1 次
{
int t = -1;
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[j] < dist[t]))
t = j; // t 为 不在 S 集合中距离最短的点
st[t] = true; // 加入 S 集合
for (int j = 1; j <= n; j ++ ) // 更新
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
// 求 1 号点到 n 号点的最短距离
return dist[n];
}
int main()
{
cin >> n >> m;
// 稠密图用邻接矩阵存图
memset(g, 0x3f, sizeof g);
for (int i = 0; i < m; i ++ )
{
int a, b, c;
cin >> a >> b >> c;
// 因为图中可能有重边，所以只保留权值小的边
g[a][b] = min(g[a][b], c);
}
// 输出邻接矩阵，没有边的地方初始化为正无穷
for (int i = 1; i <= 4; i ++ ) {
for (int j = 1; j <= 4; j ++ )
printf("%10d ", g[i][j]);
cout << endl;
}
int t = dijkstra();
if (t == INF) cout << -1 << endl;
else cout << t << endl;
return 0;
}
堆优化版 Dijkstra
const int N = 1e6 + 10, INF = 0x3f3f3f3f;
typedef pair<int, int> PII; // first 存储距离，second 存储结点编号
priority_queue<PII, vector<PII>, greater<PII>> heap; // 小根堆
int n, m, dist[N], st[N], h[N], e[N], w[N], ne[N], idx; // 稀疏图用邻接表存图
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
heap.push({0, 1}); // 把起点加入到优先队列中
while (heap.size())
{
auto t = heap.top(); // 取出堆顶
heap.pop();
int ver = t.second;
if (st[ver]) continue; // 如果访问过就不重复访问
st[ver] = true;
for (int i = h[ver]; ~i; i = ne[i])
{
int j = e[i];
// 更新
if (dist[j] > dist[ver] + w[i])
{
dist[j] = dist[ver] + w[i];
heap.push({dist[j], j});
}
}
}
// 求 1 号点到 n 号点的最短距离
return dist[n];
}
2. Bellman-Ford 算法与 SPFA 算法
Bellman-Ford 算法可以求解带有负权边的单源最短路径。
Bellman-Ford 算法的步骤非常简单，就是迭代 $n - 1$ 次，依次扫描每条边，如果边能够被更新的，就更新一下每条边。具体的：对于每条边 $(x, y, w)$，如果 $dist[y] > dist[x] + w$，则用 $dist[x] + w$ 更新 $dist[x]$。这种更新方法被称为松弛操作。
迭代结束之后，如果每条边都满足 $dist[y] \leq dist[x] + w$，则所有边都满足三角不等式性质。
Bellman-Ford 算法的时间复杂度为 $\mathcal{O}(nm)$。
队列优化版的 Bellman-Ford 算法在国内被称为 SPFA 算法。SPFA 的优化思路是对上面的松弛操作做优化，因为不一定所有的边都会被松弛，只有当前结点的出边变小了，当前结点才有可能被更新。
SPFA 算法的流程为：
- 建立一个队列，最初把起点入队
- 当队列非空，取出队头并弹出队头
- 更新队头的所有出边 $(t, y, w)$
- 如果队头的出边没有入队过，则把队头的出边入队
- 重复 $2 \sim 4$，直到队列为空。
SPFA 算法的期望时间复杂度为 $\mathcal{O}(m)$，但最坏情况会被卡到 $\mathcal{O}(nm)$。
C++ 代码： SPFA
const int N = 1e5 + 10, INF = 0x3f3f3f3f;
int n, m, dist[N], st[N], q[N], h[N], e[N], w[N], ne[N], idx;
int spfa()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
int hh = 0, tt = 0; // 循环队列
q[tt ++ ] = 1;
st[1] = true;
while (hh <= tt)
{
auto t = q[hh ++ ];
if (hh == N) hh = 0;
st[t] = false;
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if (!st[j])
{
q[tt ++ ] = j;
if (tt == N) tt = 0;
st[j] = true;
}
}
}
}
return dist[n];
}
Bellman-Ford 算法与 SPFA 算法一个很好的应用就是可以判断一个图中存不存在负环（一张图中存在一个环，权值之和为负数）。一般判断负环的算法选择 SPFA，因为 SPFA 的效率要远远大于 Bellman-Ford 算法。
SPFA 算法判断负环的方法有两种，分别为：
- 记录每个结点入队次数，若有某个结点入队次数大于等于结点总数，说明存在负环。
- 记录每个结点到 $1$ 号结点的最短路径包含的边数，若某个结点到 $1$ 号结点的最短路径包含的边数大于等于结点总数，也说明图中存在负环。
方法 $1$ 的原理：本质是 Bellman-Ford 算法，若经过了 $n$ 轮迭代，还有结点可以被更新的话，说明存在负环。对于 SPFA 来说，每个结点被更新一次就入队一次，如果一个结点入队的次数大于等于 $n$ 次，那么这个结点就被更新了大于等于 $n$ 次。一个结点每更新一次，这个结点的最短路径的距离就会加 $1$，那么一个结点更新 $n$ 次，说明这个结点的最短路径的距离的长度就等于 $n$，显然这条最短路径的结点个数就等于 $n + 1$。图中一共有 $n$ 个点，这个结点的最短路径中包含的结点个数大于等于 $n$ 了，根据抽屉原理，必然有两个一样的结点，说明存在一个环，根据松弛操作，这个环一定是负环。
方法 $2$ 的原理：类似于方法 $1$，原理其实也是抽屉原理，用一个 cnt 数组记录每个点的最短路径包含的边数，每松弛一次，更新一下距离并且更新一下 cnt 数组。如果 cnt[i] >= n，说明图中存在负环。
SPFA 算法判断负环推荐使用第二种，第二种的效率远远高于第一种，对于这样一张图，图中的边权都为负数，且有很多点。第一种方法需要绕环 $n$ 次才能达到一个结点入队的次数大于等于 $n$，而第二种方法则需要绕环 $1$ 次，再走一个结点就能达到一个结点的最短路径包含的边数大于等于 $n$。第一种方法的时间复杂度可以近似的看成 $\mathcal{O}(n^2)$，而第二种的时间复杂度可以近似的看成 $\mathcal{O}(n)$。
判断负环还要注意一种情况，有可能构成负环的结点不与 $1$ 号点联通，那么只把 $1$ 号点加到队列里就不能成功的找到负环。所以一种很实用的方法是最开始将所有点入队，这样就能成功的遍历到所有结点并找到负环。这种方法的一种更好的理解方式就是，设立一个虚拟源点，从虚拟源点向所有点连一条边权是 $0$ 的边。然后初始化是把虚拟源点加入队列，然后第一次迭代是把虚拟源点可以到达的点全部加入队列。所以最开始将所有点加入队列等价于在图中建立一个虚拟源点。
还需注意的一点是 SPFA 算法判断负环不需要初始化 dist 数组为正无穷，初始化任意值都没问题，因为如果图中存在负环，松弛操作一定会执行，所以所以 dist 的值初始化任意值都没问题。这里的正无穷（0x3f3f3f3f）严格意义来讲其实是有限值，为 $1061109567$。
const int N = 2010, M = 1e4 + 10, INF = 0x3f3f3f3f; // N 结点数量
int n, m, dist[N], st[N], cnt[N], q[N], h[N], e[M], w[M], ne[M], idx;
bool spfa()
{
memset(dist, 0, sizeof dist);
memset(cnt, 0, sizeof cnt);
memset(st, false, sizeof st);
int hh = 0, tt = 0; // 循环队列
for (int i = 1; i <= n; i ++ )
{
q[tt ++ ] = i;
st[i] = true;
}
int count = 0; // 计数器
while (hh != tt)
{
int t = q[hh ++ ];
if (hh == N) hh = 0;
st[t] = false;
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if ( ++ count > N) return true; // trick
if (cnt[j] >= n) return true;
if (!st[j])
{
q[tt ++ ] = j;
if (tt == N) tt = 0;
st[j] = true;
}
}
}
}
return false;
}
实际运用中 SPFA 的效率其实不是那么好，这里有个经验上的做法，如果 SPFA 的效率很低的时候，就认为有负环。这里的技巧是：当所有点的总共入队次数超过一个定值的时候，就认为有负环。定值经验上取 $2 \times n$ 或 $3 \times n$。