1.前言
当大家学会了floyd、Dijkstra和SPFA时，可能会好奇，Dijkstra和SPFA都是单源最短路，floyd是多源最短路，但是它的时间复杂度是O(),那有没有时间复杂度更低,而且能处理负权的多源最短路呢？
2.引入
如果我们不能使用floyd，那么我们的多源最短路应该怎么求呢？肯定是跑n次SPFA，但是很明显，时间复杂度为O(),还不如floyd的时间复杂度。那如果每条边的权值肯定不是负数呢，跑n次堆优化的Dijkstra，时间复杂度是O(
),这样一来时间复杂度得到了优化,但是如何把每条边都变成正数呢?
3.Johnson思路
先建一个超级源点--0，然后向每一个节点建一条边，每条边的边权为零。
定义h(i),代表从超级源点到i的最短路
根据上图所示,我们可以算出来h(i):
| 1 | 2 | 3 | 4 | 5 |
| 0 | -5 | 0 | -3 | 0 |
拿h(2)举个例子:(下图中红色是最短路径)
这里我们就跑一次SPFA,初始化出h[i]
然后,w'(u,v) = w(u,v)+h[u]-h[v]
更新其他边的长度,这样一来所有边都变成了正数
证明：
w(u,v)+h[u]-h[v]一定不是负数
h[v]通过这条路进行更新 -> h[v]=h[u]+w(u,v)
如果没有通过这条路进行更新的话, 那么代表h[v]肯定是短于h[u]+w(u,v)才不从u更新的
即：h[v] <= h[u]+w(u,v)
也就是0 <= h[u]+w(u,v)-h[v]
既然都大于等于零了就一定不是负数
现在所有值都变成正数了，用Dijkstra跑N遍最短路,
最后的输出dis’[u][v]-h[u]+h[v](因为我们要把它的边权改过了,我们要给它复原成原来的最短路)
证明二：原来的图的最短路dis与新图dis‘的关系是dis[u][v]=dis’[u][v]-h[u]+h[v]
假设最短路路径是u->a->b->c->...->z->v
那路权是w'(u,a)+w'(a,b)+w'(b,c)+...+w'(z,v)
展开得到
w(u,a)+h[u]-h[a]+w(a,b)+h[a]-h[b]+w(b,c)+h[b]-h[c]+...+w(z,v)+h[z]-h[v]
发现可以抵消得到
w(u,a)+w(a,b)+w(b,c)+...+w(z,v)+h[u]-h[v]
w(u,a)+w(a,b)+w(b,c)+...+w(z,v)是原来最短路的值，即dis[u][v]
替换可得
dis[u][v] +h[u]-h[v] = dis’[u][v]
也就是
dis[u][v]=dis’[u][v]-h[u]+h[v]
4.Johnson实现
P5905 【模板】全源最短路（Johnson）
题目中还有有负环的情况，这种情况可以通过SPFA判断,通过进队次数,判断是否有负环,一个点最多进队过n-1次(其他所有的元素都维护了一下它)这里实现还是挺简单的
接下来就是SPFA的代码:
int SPFA(){int v[3004] = {0};for (int i = 1; i <= n; i++){h[i] = 1e18;//初始化}h[0] = 0;v[0] = 1;int cnt[3004] = {0};//每一个点的入队次数cnt[1] = 1;queue q;q.push(0);while (!q.empty()){int x = q.front();q.pop();v[x] = 0;for (int i = 0; i < a[x].size(); i++){int y = a[x][i].y;if (h[x]+a[x][i].w < h[y]){h[y] = h[x]+a[x][i].w;if (!v[y]){cnt[y]++;if (cnt[y] > n-1){//超过n-1即为负环return 1;}v[y] = 1;q.push(y);}}}}return 0;
} 以及我前面定义的一些变量
struct node{int y,w;//增加了一个边权(w)
};
vector a[30005];
int h[3004];//这里我们就跑一次SPFA,初始化出h[i]
int dis[3004];
int vis[3004];
int n,m; 然后是Dijkstra
void dij(int st){priority_queue,vector>,greater>> pq;for (int i = 1; i <= n; i++){dis[i] = 1e18;//初始化}memset(vis,0,sizeof(vis));dis[st] = 0;pq.push({0,st});//{权，序号}while (!pq.empty()){int jin = pq.top().second;pq.pop();if (vis[jin] == 1){continue;}for (int j = 0; j < a[jin].size(); j++){int v = a[jin][j].y;int w = a[jin][j].w;if (dis[jin]+w < dis[v]){dis[v] = dis[jin]+w;pq.push({dis[v],v});}}vis[jin] =1;}
} 主函数部分
signed main(){cin >> n >> m;for (int i = 1; i <= m; i++){int u,v,w;cin >> u >> v >> w;a[u].push_back({v,w});}for (int i = 1; i <= n; i++){a[0].push_back({i,0});//我们建一个超级源点,向每一个点建一条边,而这条边的权值为零,}if (SPFA()){cout << -1;return 0;}for (int x = 1; x <= n; x++){for (int i = 0; i < a[x].size(); i++){int y = a[x][i].y;a[x][i].w += h[x]-h[y];//然后,w'(u,v) = w(u,v)+h[u]-h[v]}}
//现在所有值都变成正数了用迪杰斯特拉跑N遍最短路,for (int i = 1; i <= n; i++){dij(i);long long cnt = 0;for (int j = 1; j <= n; j++){if (dis[j] >= 1e17){//不可能满足cnt += 1e9 * j;}else{cnt += 1LL*(dis[j] - h[i] + h[j])*j;//最后的输出dis’[u][v]-h[u]+h[v]}}cout << cnt << "\n";}return 0;
}整体代码：
#include
using namespace std;
#define int long long
struct node{int y,w;
};
vector a[30005];
int h[3004];//这里我们就跑一次SPFA,初始化出h[i]
int dis[3004];
int vis[3004];int n,m;
int SPFA(){int v[3004] = {0};for (int i = 1; i <= n; i++){h[i] = 1e18;//初始化}h[0] = 0;v[0] = 1;int cnt[3004] = {0};//每一个点的入队次数cnt[1] = 1;queue q;q.push(0);while (!q.empty()){int x = q.front();q.pop();v[x] = 0;for (int i = 0; i < a[x].size(); i++){int y = a[x][i].y;if (h[x]+a[x][i].w < h[y]){h[y] = h[x]+a[x][i].w;if (!v[y]){cnt[y]++;if (cnt[y] > n-1){//超过n-1即为负环return 1;}v[y] = 1;q.push(y);}}}}return 0;
}
void dij(int st){priority_queue,vector>,greater>> pq;for (int i = 1; i <= n; i++){dis[i] = 1e18;//初始化}memset(vis,0,sizeof(vis));dis[st] = 0;pq.push({0,st});//{权，序号}while (!pq.empty()){int jin = pq.top().second;pq.pop();if (vis[jin] == 1){continue;}for (int j = 0; j < a[jin].size(); j++){int v = a[jin][j].y;int w = a[jin][j].w;if (dis[jin]+w < dis[v]){dis[v] = dis[jin]+w;pq.push({dis[v],v});}}vis[jin] =1;}
}
signed main(){cin >> n >> m;for (int i = 1; i <= m; i++){int u,v,w;cin >> u >> v >> w;a[u].push_back({v,w});}for (int i = 1; i <= n; i++){a[0].push_back({i,0});//我们建一个超级原点,向每一个点建一条边,而这条边的权值为零,}if (SPFA()){cout << -1;return 0;}for (int x = 1; x <= n; x++){for (int i = 0; i < a[x].size(); i++){int y = a[x][i].y;a[x][i].w += h[x]-h[y];//然后,w'(u,v) = w(u,v)+h[u]-h[v]}}
//现在所有值都变成正数了用迪杰斯特拉跑N遍最短路,for (int i = 1; i <= n; i++){dij(i);//最后的输出dis’[u][v]-h[u]+h[v]long long cnt = 0;for (int j = 1; j <= n; j++){if (dis[j] >= 1e17){cnt += 1e9 * j;}else{cnt += 1LL*(dis[j] - h[i] + h[j])*j;}}cout << cnt << "\n";}return 0;
}