[算法][图论] 约翰逊 Johnson 算法全源最短路

Lastmod: 2020-11-18 周三 22:20:21

约翰逊 Johnson 算法全源最短路

对于最短路问题，我们的常用算法是 Dijkstra 算法或 Bellman-Ford 算法。但这两个算法经常解决的是单源最短路问题。

对于多源（全源）最短路问题，我们有一个基于动态规划的优秀算法，Floyd-Warshall 算法。

但 Floyd-Warshall 算法是一个更适合稠密图的算法，若设 $V$ 表示图中点数 $E$ 为图中边数，则复杂度为 $O(V^3)$ 是一个与边无关的量。

对于稀疏图，$E$ 与 $V$ 同阶的情形，此时我们发现如果图是非负权图，我们可以用以每个点为起点的方式跑 $V$ 次 Dijkstra 算法，从而得到一个时间复杂度更好的算法。考虑 $E$ 和 $V$ 都是 $O(N)$ 的，则用 std::priority_queue 优化的 Dijkstra 跑 $V$ 次的时间复杂度为 $O(V((E+V) \log E)) = O(N^2 \log N)$ 是明显优于 Floyd-Warshall 的 $O(V^3) = O(N^3)$ 的。

所以此时问题来了，Floyd-Warshall 是适用于有负权图的，那么对于稀疏带负权的图我们能得到一个更好的复杂度的算法吗？

SPFA 它又死了

我们知道 Bellman-Ford 算法有一个队列优化的版本叫 Shortest Path ~~Fast~~ Foolish Algorithm，它的复杂度并不是 $O(kV)$ 的，而我们总可以通过构造数据（网格图）使得它跑到 $O(VE)$。所以跑 $V$ 轮 Bellman-Ford 不会取得更好的时间复杂度，$O(VVE) = O(N^3)$。

所以我们还得想办法让 Dijkstra 能用，或者是发明新算法。

修改边权赐予 Dijkstra 战胜负权图的力量

Johnson 算法的一个核心就是对所有边权重新标记。新标号的边权是非负的从而使得 Dijkstra 在新图上可用。

首先我们知道，简单的给所有的边加上最小权重的相反数这个肯定是行不通的，这样我们会引入边数这个新的影响因素，例如以前最短路可能是一条边数很多但边权和很小的路径，比如权重和为 $sum_0$ 边数为 $n_0$，考虑另一路径，权重和为 $sum_1$ 边数为 $n_1$，且 $sum_1 \ge sum_0$，$n_1 \le n_2$。在权重都增加 $\delta > 0$ 后有 $sum_0' = sum_0 + n_0\delta$， $sum_1' = sum_1 + n_1\delta$，此时我们发现 $sum_0'$ 和 $sum_1'$ 的大小关系是不确定的，也就是原图的最短路未必对应新图的最短路，也就是说这样的标号方案是不正确的。

那么如何修改边权能不改变原图的最短路呢？

这里我们引入一个类似势能和每个点绑定的值 $h[i]$。

考虑边 $<u,v>$ 权重为 $w(u,v)$，重新标记边权为

$$w'(u,v) = w(u,v) + h[u] - h[v]$$

这样标记的好处是对于一条路径 $v_0, v_1, v_2, \cdots,v_n$，原图上的长度为，

$$sum = w(v_0,v_1) + w(v_1,v_2) + \cdots + w(v_{n-1},v_{n})$$

而新图上的长度是

$$ \begin{align} sum' =& w'(v_0,v_1) + w'(v_1,v_2) + \cdots + w'(v_{n-1},v_{n}) \\ =& (w(v_0,v_1)+h[v_0]-h[v_1]) + (w(v_1,v_2)+h[v_1]-h[v_2]) + \cdots + (w(v_{n-1},v_n)+h[v_{n-1}]-h[v_n]) \\ =& (w(v_0,v_1) + w(v_0,v_1) + \cdots + w(v_{n-1},v_n)) + (h[v_0]-h[v_1]+h[v_1]-h[v_2]+ \cdots +h[v_{n-1}]-h[v_n]) \\ =& sum + h[v_0] - h[v_n] \end{align} $$

我们发现原图与新图路径长度的差值其实只与起止位置有关，与路径无关。此时我们发现原图最短路和新图的最短路的选择是等价的。

假设原图上 $v_0$ 到 $v_n$ 的最短路之一是路径 $v_0, v_1, v_2, \cdots,v_n$ 其权值和是 $sum_0$，此时新图上显然也可以选取这一路径得到 $sum_0' = sum_0 + h[v_0] - h[v_n]$。我们只需证明这个在新图上也是最短路即可。假设这条路径在新图上并非最短路，新图有一条更短的路径 $v_0, u_1, u_2, \cdots, v_n$ 其权重为 $sum_1' < sum_0'$ 这时我们发现，必然在原图上这条路径可以得到

$$sum_1 = sum_1'-(h[v_0]-h[v_n]) < sum_0' - (h[v_0]-h[v_n]) = sum_0$$

也就是说我们在原图上得到了一条比最短路更短的路径，这显然与假设是相违背的。

现在的问题就变成了，我们怎么能推算一套 $h[i]$ 使得所有的 $w'(u,v) \ge 0$。

这相当于我们要

$$w'(u,v) = w(u,v) + h[u] - h[v] \ge 0$$

即

$$w(u,v) \ge h[v] - h[u]$$

仔细盯着这个式子观察，发现，这不就是最短路跑完时边与距离的三角不等式么！

$$w(u,v) \ge dis[v] - dis[u]$$

那我们用最短路的结果 $dis[i]$ 当做 $h[i]$ 标号就好了么。

但，我们不是要做的就是最短路吗，这不是坑爹么！

也对，但也不对，此最短路非彼最短路。因为标号只需要一次就够了，我们随便做一次可以跑到所有点的最短路即可。而我们最终要求的全源最短路需要跑 $V$ 轮。

于是，

Bellman-Ford 它还活着

我们可以加一个超级源点 $src$ 向所有点连权重为 $0$ 的边，然后跑一遍 Bellman-Ford，得到 $h$ 数组。这样我们就能够处理负权图了。

一次 Bellman-Ford 算法的复杂度虽然高，但是 Dijkstra 要跑 $V$ 轮，这部分才是主导时间复杂度的部分。这也是为什么我们无法通过这种标号的方法使得在一般最短路问题中 Dijkstra 算法可用。

这里特别注意的是，由于有负环图 Bellman-Ford 算法其实是结束不了的（最短路不存在），因此对于这样的图是没法进行标号的。

至此我们得到了一个完美的稀疏图上的全源最短路算法 $Johnson$ 算法。

Johnson 算法

算法流程

建立超级源点 $src$ 向所有的点连一条权重为 $0$ 的有向边（这样其他点不会走到 $src$）。
以 $src$ 为源点跑 Bellman-Ford 确定图中是否有负环并确定 $h[i]$ 的值，有负环直接结束
以每一个原图中的点为起点，以 $w(u,v) + h[u] - h[v]$ 为边的权重跑 $V$ 次 Dijkstra
得到的距离数组 $dis[u][v]$ 需要 $-h[u]+h[v]$ 才能得出真实的距离，注意特殊处理无法走到的情况的值

标号及最短路长度范围

注意原图可能存在非常长的负权路径，因此如果边权范围是 $[-C,C]$ 则 $h[i]$ 的范围可能达到 $[-C(V-1),0]$ 而 $w'$ 的范围则是 $[0,CV]$，不过虽然边权范围很宽，但新图上最短路的长度也并不会达到 $CV^2$，考虑原图最短路最长也就是 $C(V-1)$ 则新图最短路不会超过 $C(V-1) + h_{max} - h_{min} = 2 C(V-1)$。

复杂度

空间复杂度：Bellman-Ford 我们只需要一个额外的 $h$ 数组，Dijkstra 需要 $O(V)$ 的空间不赘述。如果每一轮我们都直接将求出的最短路都输出而不是存在一个 $O(V^2)$ 的数组中的话，那么额外空间就是 $O(V)$ 的，存图的空间为 $O(V+E)$ 总复杂度为 $O(V+E)$。

时间复杂度：Bellman-Ford 为 $O(VE)$ 。如果使用 std::priority_queue 优化的 Dijkstra 则总复杂度为 $O(V(E+V)\log E)$。

例题及代码

Luogu P5905

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
const int M=3005;
const int INF=1e9;
vector<PII> g[M];
int h[M];
int n,m;
int src;

bool bellman_ford()
{
	for(int i=0;i<=n;i++)
		h[i]=INF;
	h[src]=0;
	for(int i=1;i<n;i++)
		for(int u=0;u<=n;u++)
		{
			if(h[u]==INF) continue;
			for(auto [v,w]:g[u]) h[v]=min(h[v],h[u]+w);
		}
	int f=1;
	for(int u=0;u<=n&&f;u++)
	{
		if(h[u]==INF) continue;
		for(auto [v,w]:g[u]) if(h[v]>h[u]+w) { f=0; break; }
	}
	return f;
}

int dis[M];
int vis[M];
priority_queue<PII,vector<PII>,greater<PII>> qu;
LL dijkstra(int st)
{
	for(int i=1;i<=n;i++)
		dis[i]=INF,vis[i]=0;
	while(!qu.empty()) qu.pop();
	qu.emplace(0,st);
	dis[st]=0;
	while(!qu.empty())
	{
		PII p=qu.top(); qu.pop();
		int u=p.second;
		if(vis[u]) continue;
		vis[u]=1;
		for(auto [v,w]:g[u])
		{
			w+=h[u]-h[v];
			// cout<<w<<endl;
			if(vis[v]) continue;
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				qu.emplace(dis[v],v);
			}
		}
	}
	LL ans=0;
	for(int i=1;i<=n;i++)
		if(dis[i]==INF) ans+=1LL*i*INF;
		else ans+=1LL*i*(dis[i]-h[st]+h[i]);
	return ans;
}

int main()
{
	scanf("%d%d",&n,&m);
	int u,v,w;
	for(int i=0;i<m;i++)
	{
		scanf("%d%d%d",&u,&v,&w);
		g[u].emplace_back(v,w);
	}
	src=0;
	for(int i=1;i<=n;i++)
	{
		g[src].emplace_back(i,0);
	}
	if(!bellman_ford())
	{
		printf("-1\n");
		return 0;
	}
	for(int i=1;i<=n;i++)
		printf("%lld\n",dijkstra(i));
	return 0;
}

Prev: [模板][数论] 扩展欧几里得算法（ExGCD）
Next: [模板][数据结构] 离散化 Discretization

约翰逊 Johnson 算法 全源最短路