一、算法简析

\(Johnson\) 算法可以求解带负权边的中小图的全源最短路径。

算法步骤：

• 建立虚拟源点 \(0\)，从 \(0\) 至其它各点添加权值为 \(0\) 有向边。
• 用 \(spfa\) 算法求出从 \(0\) 至其它各点的最短路径 h[i]。
• 将原图中边的权值改为：\(w(u,v)+h[u]-h[v]\)，建立了一张新图。
• 以各点为源点，运行 \(n\) 轮 \(Heap-Dijkstra\) 算法，求出新图中任意两点间的最短路径。再通过下文的公式，求出原图中任意两点间的最短路径。

规定：\(w(u,v)\) 和 \(w'(u,v)\) 分别表示原新图中有向边 \(e(u,v)\) 的权值；\(d(s,t)\) 和 \(d'(s,t)\) 分别表示原新中 \(u\) 到 \(v\) 的最短路径。

• 公式一：

注：新图一定满足 \(w'(u,v)\geq 0\)，即新图没有负边权。

• 公式二：

注：我们求出 \(s\) 为源点的新图中的最短路径 d[t] 后，通过 \(d[t]+h[t]-h[s]\) 求出原图中的最短路径。

Code

P5905 【模板】全源最短路（Johnson）

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll quickin(void)
{
	ll ret = 0;
	bool flag = false;
	char ch = getchar();
	while (ch < '0' || ch > '9')
	{
		if (ch == '-')    flag = true;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9' && ch != EOF)
	{
		ret = ret * 10 + ch - '0';
		ch = getchar();
	}
	if (flag)    ret = -ret;
	return ret;
}

struct edge{int to, worth;};
typedef pair<int, ll> P;
const int MAX = 3e3 + 5;
const ll INF = 1e9;
int N, M;
vector<edge> G[MAX];
bool vis[MAX];
int cnt[MAX];                // cnt[i] -- s到i经过的边数 
ll d[MAX], h[MAX];           // d[i]/h[i] -- s到i的最短路径 

void spfa(void)
{
	fill(vis, vis + 1 + N, false);
	fill(h, h + 1 + N, INF);
	queue<int> Q;
	
	h[0] = 0, vis[0] = true, Q.push(0);
	while (!Q.empty())
	{
		int u = Q.front();
		Q.pop();
		vis[u] = false;
		
		for (auto e : G[u])
		{
			int v = e.to;
			ll w = e.worth;
			
			if (h[v] > h[u] + w)
			{
				h[v] = h[u] + w;
				cnt[v] = cnt[u] + 1;
				if (cnt[v] > N)
				{
					cout << "-1" << endl;
					exit(0);
				}
				
				if (!vis[v])
				{
					Q.push(v);
					vis[v] = true;
				}
			}
		}
	}
}

struct cmp
{
	bool operator()(const P &a, const P &b)
	{
		return a.second > b.second;		
	}	
};

void dijkstra(int s)
{
	fill(vis + 1, vis + 1 + N, false);
	fill(d + 1, d + 1 + N, INF);
	priority_queue<P, vector<P>, cmp> Q;
	
	d[s] = 0, Q.push(P(s, 0));
	while (!Q.empty())
	{
		P p = Q.top();
		Q.pop();
		int u = p.first;
		
		if (vis[u])    continue;
		vis[u] = true;
		
		for (auto e : G[u])
		{
			int v = e.to;
			ll w = e.worth;
			
			if (d[v] > d[u] + w)
			{
				d[v] = d[u] + w;
				if (!vis[v])    Q.push(P(v, d[v]));
			}
		}
	}
}

int main()
{
	#ifdef LOCAL
	freopen("test.in", "r", stdin);
	#endif
	
	N = quickin(), M = quickin();
	for (int i = 0; i < M; ++i)
	{
		int a, b, c;
		a = quickin(), b = quickin(), c = quickin();
		G[a].push_back(edge{b, c});
	}
	// 建虚拟源节点0，从0至各点加权值为0的边
	for (int i = 1; i <= N; ++i) 
		G[0].push_back(edge{i, 0});
	
	// 计算0到各节点的最短路径h[]	
	spfa();
	
	// 构造新边
	for (int i = 1; i <= N; ++i)
		for (auto &e : G[i])
			e.worth += h[i] - h[e.to];
			
	for (int i = 1; i <= N; ++i)
	{
		// 在新图上，计算i到各点的最短路径
		dijkstra(i);
		
		ll ans = 0;
		for (int j = 1; j <= N; ++j)
		{
			if (d[j] == INF)    ans += j * INF;
			else    ans += j * (d[j] + h[j] - h[i]); // 原图上的最短路径 
		}
		cout << ans << endl;
	}
	
	return 0;
}

完