在看到这篇文章前，请确保你已经学习过Dijkstra和Bellman-Ford算法（用SPFA也行）。
johnson用于解决存在负权的全源最短路问题，时间复杂度为，比对所有点跑一遍Bellman-Ford（可以判断负权图，但是如果对每个点求一次单源最短路时间复杂度为）要快。
本篇文章会分三部分讲解Johnson算法，其中第一、二部分是算法实现流程，第三部分是原理解释。
题目背景是求解类似以下稀疏图的全源最短路，点的个数，边数，典型的稀疏图。
可以做一下这个例题：www.luogu.com.cn/problem/P5905
1.re-weight operation
re-weight，顾名思义就是重新调整每条边的权重。
对于一个图，我们先建立一个"Super Source Node"（超级源点），我们用0号节点表示，并且将其与所有点连接起来，边权为0。
接下来用Bellman-Ford算法计算出超级源点的单源最短路，这个是很简单的。
ll h[N];//h[x]表示源点0到到x的最短距离，通过Bellman-Ford计算
bool Bellman_Ford()
{
//初始化h[]为无穷
for(int i = 1;i <= n; ++ i)h[i] = inf;
//松弛n-1次，i仅用于计数
for(int i = 1;i < n; ++ i)
{
//枚举所有边，尝试用这条边去松弛点x
for(const auto &[x, y, w] : es)
{
if(h[x] == inf)continue;
//如果可以通过这条边可以松弛
if(h[x] + w < h[y])
{
h[y] = h[x] + w;
}
}
}
//判断是否存在负权环
for(const auto &[x, y, w] : es)
{
if(h[x] == inf)continue;
//如果还有边可以松弛，那么说明存在负环返回false
if(h[x] + w < h[y])return false;
}
//不存在负环，返回true
return true;
}好，假如不存在负环，现在我们就得到了一个数组对吧，接下来我们令每条边的权重。
这样一定可以使得所有边权都为正权，假如，那么必然有，于是有。
2.run Dijkstra Alogorithm
在此基础上去对每一个点跑一遍Dijkstra算法，即可求得对于每一个点的单源最短路，而求出来的这个距离d(u, v)实际上是进行了偏移之后的，要还原为真实的距离还要令：f(u, v) = d(u, v) - h[u] + h[v]。
直接看代码（这里就不写注释了）：
void dijkstra(int st)
{
static ll d[N];
for(int i = 1;i <= n; ++ i)d[i] = inf;
bitset<N> vis;
priority_queue<Node> pq;
pq.push({st, d[st] = 0});
while(pq.size())
{
int x = pq.top().x;pq.pop();
if(vis[x])continue;
vis[x] = true;
for(const auto &[y, w] : g[x])
{
if(d[x] + w < d[y])
{
d[y] = d[x] + w;
pq.push({y, d[y]});
}
}
}
for(int i = 1;i <= n; ++ i)dis[st][i] = d[i];
}3.原理解释
注意我们第一次求的数组，为什么不直接d用来表示呢？因为在物理中h的含义是“势能”，我们将一个物理含义挪用到信息学中，可以形象的解释h数组的含义。
b站贴latex太吃史了，直接看图。
例题的代码：
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 3e3 + 9;
const ll inf = 1e9;
ll n, m;
struct Edge
{
ll x, y, w;
};
vector<Edge> es;
struct Node
{
ll x, w;
bool operator < (const Node &u)const
{
return w == u.w ? x < u.x : w > u.w;
}
};
vector<Node> g[N];
ll h[N];//h[x]表示源点0到到x的最短距离，通过Bellman-Ford计算
ll dis[N][N];
bool Bellman_Ford()
{
//初始化h[]为无穷
for(int i = 1;i <= n; ++ i)h[i] = inf;
//h[0] = 0这个可以忽略
//一共(n+1)个点，所以松弛n次，i仅用于计数
for(int i = 1;i <= n; ++ i)
{
//枚举所有边，尝试用这条边去松弛点x
for(const auto &[x, y, w] : es)
{
if(h[x] == inf)continue;
//如果可以通过这条边可以松弛
if(h[x] + w < h[y])
{
h[y] = h[x] + w;
}
}
}
//判断是否存在负权环
for(const auto &[x, y, w] : es)
{
if(h[x] == inf)continue;
//如果还有边可以松弛，那么说明存在负环返回false
if(h[x] + w < h[y])return false;
}
//不存在负环，返回true
return true;
}
void dijkstra(int st)
{
static ll d[N];
for(int i = 1;i <= n; ++ i)d[i] = inf;
bitset<N> vis;
priority_queue<Node> pq;
pq.push({st, d[st] = 0});
while(pq.size())
{
int x = pq.top().x;pq.pop();
if(vis[x])continue;
vis[x] = true;
for(const auto &[y, w] : g[x])
{
if(d[x] + w < d[y])
{
d[y] = d[x] + w;
pq.push({y, d[y]});
}
}
}
for(int i = 1;i <= n; ++ i)dis[st][i] = d[i];
}
void solve()
{
cin >> n >> m;
for(int i = 1;i <= m; ++ i)
{
ll u, v, w;cin >> u >> v >> w;
g[u].push_back({v, w});
es.push_back({u, v, w});
}
for(int i = 1;i <= n; ++ i)es.push_back({0, i, 0});
if(!Bellman_Ford())
{
cout << -1 << '\n';
return;
}
//求出h[]数组后，0号点已经没用了
//1.re-weight
for(int x = 1;x <= n; ++ x)
{
for(auto &[y, w] : g[x])
{
w = w + h[x] - h[y];
}
}
//2.run Dijkstra
for(int x = 1;x <= n; ++ x)dijkstra(x);
//3.calculate the Sum
for(int i = 1;i <= n; ++ i)
{
ll sum = 0;
for(int j = 1;j <= n; ++ j)
{
if(dis[i][j] == inf)sum += 1ll * j * inf;
else sum += 1ll * j * (dis[i][j] - h[i] + h[j]);
}
cout << sum << '\n';
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int _ = 1;
while(_ --)solve();
return 0;
}留到最后
非常感谢你看到这里，我是ErikTse，一名致力于做优质计算机教程的UP主~
欢迎关注我的账号，学习更多ACM算法、计算机编程相关知识~
如果你是正在准备算法竞赛的新手，或者是想要通过算法相关考试的同学，欢迎进入我的b站个人主页，了解我的《算法基础课》（39元超值），或在【爱发电】网页/APP中搜索【Erik_Tse】了解详情（这里价格更低）。
