有关Johnson算法

提到多源最短路，你可能会想到Floyd或跑n遍单源最短路

但Floyd O(\(n^3\))的复杂度无法接受

关于SPFA他已经死了,会被卡到O(\(n^2m\))

那么考虑Dij，n遍Dij是的复杂度是O(nm\(\log(n)\)),很不错，但不能处理负边权，我们就考虑如何修改权值，在不影响最短路的前提下，使边权为正。

注意：不能直接使所以边加上一个数使边权变正

因为所走的边的个数不一样，可能看过Johnson的正确性证明可以明白

我们提供一种解决方法：

先建一个超级起点，连接上每一个点，跑一边最短路，得到距离s的最短路数组h[i]。
对于任意权值w(x,y)修改成w(x,y)+h[x]-h[y].

正确性证明：

我们需要证明两个东西

1. 修改完边权后的最短路径还是原来的最短路径

对于任意一条路径s->\(p_1\)->\(p_2\)->\(p_3\)->......->t

原权值为w(s,\(p_1\))+w(\(p_1\),\(p_2\))+w(\(p_2\),\(p_3\))+......+w(\(p_k\),t)

修改后为w(s,\(p_1\))+h[s]-h[\(p_1\)]+w(\(p_1\),\(p_2\))+h[\(p_1\)]-h[\(p_2\)]+w(\(p_2\),\(p_3\))+h[\(p_2\)]-h[\(p_3\)]+......+w(\(p_k\),t)+h[\(p_k\)]-h[t]

可以发现中间的权值都被消除最后只剩下w(s,\(p_1\))+w(\(p_1\),\(p_2\))+w(\(p_2\),\(p_3\))+......+w(\(p_k\),t)+h[s]-h[t]

因为图是固定的的，所以h数组是固定的，则h[s]-h[t]为固定的，所以修改完边权后的最短路径还是原来的最短路径

2. 权值为正

因为h数组满足最短路的性质，对于任意w(x,y)都有$ h[y]\leq h[x]+w(x,y) \(所以\) w(x,y)+h[x]-h[y] \geq 0 $，故成立。

所以只要跑一遍SPFA处理h数组，再跑nj遍Dij就可以A掉这到绿题。

记得开long long

记得看清求得是$ \sum_{i=1}^n j*dis_{i,j}$

附上代码

#include<bits/stdc++.h>
using namespace std;
#define val a[x][i].second
#define to a[x][i].first
#define P pair<int,int>
vector<pair<int,int> > a[3010];
queue<int> qq;
const int N=1e4;
priority_queue<P,vector<P>,greater<P> > q;
long long ans,d[N],dis[N];
int v[N],f[N];
int n,m,x,y,z;
bool spfa()
{
	memset(dis,0x3f,sizeof(dis));
	qq.push(0);
	dis[0]=0;
	v[0]=1;
	while(!qq.empty())
	{
		int x=qq.front();
		qq.pop();
		v[x]=0;
		for(int i=0;i<a[x].size();i++)
		{
			if(dis[to]>dis[x]+val)
			{
				dis[to]=dis[x]+val;
				if(!v[to])
				{
					qq.push(to);
					v[to]=1;
				}
				f[to]=f[x]+1;
				if(f[to]>n+1)
				return 0;
			}
		}
	}
	return 1;
}
void DIJ(int s)
{
	memset(dis,0x3f,sizeof(dis));
	memset(v,0,sizeof(v));
	dis[s]=0;
	q.push(P(0,s));
	while(!q.empty())
	{
		int x=q.top().second;
		q.pop();
		if(v[x])
		continue;
		v[x]=1;
		for(int i=0;i<a[x].size();i++)
		{
			if(dis[to]>dis[x]+val)
			{
				dis[to]=dis[x]+val;
				q.push(P(dis[to],to));
			}
		}
	}
}
int read() {
	int x = 0, f = 1, ch = getchar();
	while(!isdigit(ch)) {if(ch == ‘-‘) f = -1; ch = getchar();}
	while(isdigit(ch)) x = (x << 1) + (x << 3) + ch - ‘0‘, ch = getchar();
	return x * f;
}
int main()
{
	n=read();m=read();
	for(int i=1;i<=m;i++)
	{
		x=read();y=read();z=read();
		a[x].push_back(P(y,z));
	}
	for(int i=1;i<=n;i++)
	{
		a[0].push_back(P(i,0));
	}
	if(spfa()==0)
	{
		cout<<"-1";
		return 0;
	}
	for(int i=1;i<=n;i++)
	{
		d[i]=dis[i];
	}
	for(int x=1;x<=n;x++)
	{
		for(int i=0;i<a[x].size();i++)
		{
			val+=dis[x]-dis[to];
		}
	}
	for(int i=1;i<=n;i++)
	{
		DIJ(i);
		ans=0;
		for(int j=1;j<=n;j++)
		{
			if(dis[j]>=0x3f3f3f3f)
			ans+=j*1e9;
			else
			ans+=j*(dis[j]-d[i]+d[j]);
		}
		printf("%lld\n",ans);
	}
	return 0;
}

欢迎大佬来指错

P5905【模板】Johnson 全源最短路 题解

原文：https://www.cnblogs.com/floatbamboo/p/15022490.html