再谈 Johnson 算法求最短路
clx201022
·
·
算法·理论
引入
前置知识：Dijkstra 和 Bellman–Ford。
有时，我们会需要求一个带负权边的稀疏图的全源最短路，并且出题人非常毒瘤，把 n 轮 Bellman–Ford 的所有优化全部卡掉了。
部分数据卡 n 轮 SPFA 算法。
这个时候，我们就要使用 Johnson 算法求最短路。
该算法在 1977 年由 Donald B. Johnson 提出。
虽然 1977 年该算法就被提出，但还是困扰了笔者很长一段时间。今天，我决定将自己的感悟写在这，争取能让初学者一看就懂。
从零开始分析
在 OI Wiki 和洛谷日报上都已经有大体的实现过程和基于势能的分析。
但是：为什么？
为什么要设一个超级源点接着连一条边权为 0 的边到所有点再跑一遍 Bellman–Ford 并将结果作为每个点的势能，再在计算边权的时候加加减减势能就可以让所有的边权非负并正确求出最短路？
为什么？难道这些过程都是自动被注意到然后就“砰”一下冒出来的吗？
这一次，笔者将从零开始分析 Johnson 算法的“势能”计算经过。
“超级源点”到底有什么用？
一个超级源点 0 连着一条边权为 0 的边到所有点。
对于任意一点 x，设其中一条 0\rightarrow x 最短路径为由边 (0,y)，y\rightarrow x 构成，因为 w(0,y)=0，所以 0\rightarrow x 和 y\rightarrow x 的最短路长度是相等的。
因此，0 到 x 的最短路可以等价地转换为从任意一点（包括 x）到 x 的最短路。
也就是说，我们利用超级源点，对于任一点 x，求出了从所有点出发到达 x 的最短路。
为了方便表述，我们设 h_x 即为从所有点出发到达 x 的最短路。
因为 h 的本质还是最短路，所以对于任意边 (u,v)，满足 h_v\le h_u+w(u,v)。（事实上，我们要的就是这个性质，所以前面的过程都是为了这碟醋包的饺子）
如何“让边权非负”？
先对于所给的图 E 找到一个新图 E'，满足 E' 中所有边权非负并对于 E 上的任意一条最短路 dis(x,y)，都可以 O(1) 地由 E' 上的 dis(x',y') 转换。
然后再用 Dijkstra 对 E' 上每一点求出单源最短路再转换到 E 上即可合成全源最短路。
问题是，我们如何才能求出这样一个 E' 呢？
因为要求 dis(x,y) 与 dis(x',y') 一一对应，不妨设 E' 与 E 结构相同，只是边权不同。
那么边权又应该如何改变呢？
不妨往简单的方向想，设其中差为 dis(x,y)-dis(x',y')=\delta(x,y)。
考虑 E 上的一条最短路径 x\rightarrow p \rightarrow y，其中 dis(x,y)=dis(x,p)+w(p,y)，此路径必然与一条 dis(x',y')=dis(x',p')+w(p',y') 相对应。
此时，dis(x,p)+w(p,y)-(dis(x',p')+w(p',y'))=\delta(x,y)，因为 dis(x,p)-dis(x',p')=\delta(x,p)，化简可得 w(p',y')=w(p,y)+\delta(x,p)-\delta(x,y)。
因此，只要找到一个合适的 \delta 函数使 w(p',y')=w(p,y)+\delta(x,p)-\delta(x,y)\ge 0，就能构造出一个边权非负的 E'。
使用瞪眼法，发现这个式子中 x 是没有限制的，也就是说 \delta(x,p)-\delta(x,y) 在任何 x 下都是相等的，因此我们甚至可以这样：w(p',y')=w(p,y)+\delta(y,p)-\delta(y,y)\ge 0，而显然 \delta(y,y)=0[^1]。
:::info[证 $\forall x[\delta(x,p)-\delta(x,y)=\delta(y,p)]$]
$$
\begin{aligned}
\delta(x,p)-\delta(x,y) &=(h_p-h_x)-(h_y-h_x) \\
&=h_p-h_y \\
&=\delta(y,p)
\end{aligned}
$$
:::
>先对于所给的图 $E$ 找到一个新图 $E'$，满足 $E'$ 中所有边权非负并对于 $E$ 上的任意一条最短路 $dis(x,y)$，都可以 $O(1)$ 地由 $E'$ 上的 $dis(x',y')$ 转换。
>
>然后再用 Dijkstra 对 $E'$ 上每一点求出单源最短路再转换到 $E$ 上即可合成全源最短路。
Accepted!
:::warning[$\delta(x,y)=h_y-h_x$ 是否存在笔误？]
没有。
这是因为其定义为 $\delta(x,y)=dis(x,y)-dis(x',y')$，因此，如果想要让 $\delta$ 函数“正过来”，只需修改定义为 $\delta(x,y)=dis(x',y')-dis(x,y)$，此时 $\delta(x,y)=h_x-h_y$。
:::
:::info[为什么又说 $h$ 是“势能”？]
>也就是说，我们利用超级源点，对于任一点 $x$，求出了从所有点出发到达 $x$ 的最短路。
>
>为了方便表述，我们设 $h_x$ 即为从所有点出发到达 $x$ 的最短路。
“势能”这一概念实际上并不在图上的某个具体点表现出来，而是整个图的一种性质：改变图上的任意一个点都可能导致整个图的 $h$ 发生变化。
感性理解，$-h$ 就相当于这个点最多可以被其他点走到的路上减去多少边权，而 $h_x-h_y=-h_y-(-h_x)$ 就相当于它由 $x$ 到 $y$ 需要多支付到 $y$ 可以减去这么多的边权的代价，同时减去 $-h_x$，即在 $x$ 可以从其他点走到 $x$ 减去多少边权。
**一旦选定了从 $x$ 到 $y$，你就放弃了其他的可能到 $y$ 的路径。**
这种理解方式也可以形象化地解释为什么 $E'$ 边权非负：因为在到每一点 $x$ 时都需要额外支付可能到达 $x$ 的最短路的代价，所以，当为最短路时，代价必然为 $0$，否则，代价必然更大，不可能为负数。
:::
## 实现
:::success[码风优良]
[P5905](https://www.luogu.com.cn/problem/P5905)
```cpp
#include <algorithm>
#include <iostream>
#include <vector>
#include <array>
#include <queue>
using namespace std;
using ll = long long;
const ll maxn = 3e3;
const ll maxm = 6e3;
struct bian
{
int v;
ll w;
bool operator<(const bian &obj) const
{
return w < obj.w;
}
bool operator>(const bian &obj) const
{
return obj < *this;
}
bian(int v_ = 0, ll w_ = 0) : v(v_), w(w_) {}
};
bool SPFA(int start, vector<ll> &dis, const vector<vector<bian>> &edge, const int n, const ll very_big = 1e9)
{
queue<int> q;
vector<int> t(n + 1, 0);
vector<bool> inq(n + 1, 0);
q.push(start);
inq[start] = 1;
dis.resize(n + 1);
for (int i = 0; i <= n; i++)
dis[i] = very_big;
dis[start] = 0;
while (!q.empty())
{
int u = q.front();
q.pop();
inq[u] = 0;
for (const bian &e : edge[u])
{
if (dis[e.v] > dis[u] + e.w)
{
dis[e.v] = dis[u] + e.w;
if (++t[e.v] > n)
return false;
if (inq[e.v])
continue;
inq[e.v] = 1;
q.push(e.v);
}
}
}
return true;
}
bool Dijkstra_for_Johnson(int start, vector<ll> &dis, const vector<vector<bian>> &edge, const int n, const vector<ll> &h, const ll very_big = 1e9)
{
priority_queue<bian, vector<bian>, greater<bian>> q;
vector<bool> vis(n + 1, 0);
q.push(bian(start, 0));
dis.resize(n + 1);
for (int i = 0; i <= n; i++)
dis[i] = very_big;
dis[start] = 0;
while (!q.empty())
{
int u = q.top().v;
q.pop();
if (vis[u])
continue;
vis[u] = 1;
for (const bian &e : edge[u])
{
const int v = e.v;
const ll w = h[u] - h[v] + e.w;
if (dis[v] > dis[u] + w)
{
dis[v] = dis[u] + w;
if (vis[v]) // 很明显出了点小问题
return false;
q.push(bian(v, dis[v]));
}
}
}
for (int i = 0; i <= n; i++)
{
if (dis[i] != very_big)
dis[i] += h[i] - h[start];
}
return true;
}
vector<vector<bian>> edge;
int main()
{
int n, m;
cin >> n >> m;
edge.resize(n + 1);
for (int i = 1; i <= m; i++)
{
int u, v;
ll w;
cin >> u >> v >> w;
edge[u].push_back(bian(v, w));
}
for (int i = 1; i <= n; i++)
{
edge[0].push_back(bian(i, 0));
}
vector<ll> h;
if (SPFA(0, h, edge, n))
{
vector<ll> dis(n + 1);
for (int i = 1; i <= n; i++)
{
if (!Dijkstra_for_Johnson(i, dis, edge, n, h))
throw runtime_error("Negative edge or other something wrong.");//抛出错误，正常不用管
ll ans = 0;
for (int j = 1; j <= n; j++)
{
ans += j * dis[j];
}
cout << ans << endl;
}
}
else
cout << -1 << endl;
return 0;
}
```
:::
### 后记
其实 Johnson 算法本身的实现并不算难，但是其中的变正为负的“势能”思想和综合两种算法优点，将问题转化的精神却并不简单。
SPFA 死了吗？
[SPFA 未死。](https://www.luogu.com.cn/article/2mldguwg)它仍活在 Johnson 中，活在每个 OI 人的心中。
[追忆](https://www.luogu.com.cn/problem/P11831)既往历史，[过去已经凝固](https://www.luogu.com.cn/article/awz9rvsq)。
向前[开创未来](https://www.luogu.com.cn/article/vwlwiejx)，而[路](https://www.luogu.com.cn/article/qxr5l6k9)就在脚下。
[^1]:一个点 $x$ 和其对应点 $x'$ 必然满足 $dis(x,x)=0,dis(x',x')=0$，否则图中必然有负环，此时最短路不存在。