Johnson算法
一、算法简析
\(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)=w(u,v)+h[u]-h[v]
\]
注：新图一定满足 \(w'(u,v)\geq 0\)，即新图没有负边权。
公式二：
\[d'(s,t)=d(s,t)+h[s]-h[t]
\]
注：我们求出 \(s\) 为源点的新图中的最短路径 d[t] 后，通过 \(d[t]+h[t]-h[s]\) 求出原图中的最短路径。
Code
P5905 【模板】全源最短路（Johnson）
#include
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
const int MAX = 3e3 + 5;
const ll INF = 1e9;
int N, M;
vector
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
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
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;
}
完