Johnson全源最短路

思路：

对于$N$个顶点$M$条边的图怎么求全源最短路？

Floyd，时间复杂度$O(N^3)$。$N$次Bellman-Ford/SPFA,以每个顶点为源点跑一遍，时间复杂度$O(N^{2}M)$,在稠密图中比Floyd还慢，即使尝试一些如SLF的玄学优化也会被特定数据卡掉。$N$次Dijkstra，时间复杂度$O(NM\log M)$,弊端是无法处理负边权。

那么是不是可以考虑把所有边权变非负？ 考虑如果每个边加一个足够大的数$x$,使所有边权变非负，可不可以？答案是不行的。因为假设存在三个点$a,b,c$,边权为$w(a,b)=k_1,w(b,c)=k_2,w(a,c)=k_3,k_1+k_2<k_3$,那么$a$到$c$最短路为$a\to b\to c$,这时候每个边权加$x$,如果存在$k_1+x+k_2+x>k_3+x$,即$x>k_3-k_1-k_2$,此时最短路就改变成了$a\to c$。 此处正文，上文只是在分析为什么错误： 这时候就需要Johnson算法了。 设一个超级源点$x_0$，与所有点建一个权值为$0$的边，求出以$x_0$为源点的单源最短路,放入数组$h$,然后对于边$(u,v)$,$w^{\prime }(u,v)=w(u,v)+h[u]-h[v]$。 1、证明$w^{\prime }(u,v)$非负： $\because w(x_0,u)+w(u,v)\ge w(x_0,v)$ $\therefore h[u]+w(u,v)\ge h[v]$ $\therefore w(u,v)+h[u]-h[v]\ge 0$ 即$w^{\prime }(u,v)\ge 0$ 2、证明路径权值和不会改变： 假设从$s$到$t$的一条路径为$s\to x_1\to x_2\to \cdots \to x_n\to t$, 则$dis(s,t)=w(s,x_1)+w(x_1,x_2)+\cdots +w(x_n,t)$ $\begin{array}{rl}di{s}^{\prime }(s,t)& =w^{\prime }(s,x_1)+w^{\prime }(x_1,x_2)+\cdots +w^{\prime }(x_n,t)\\ & =(w(s,x_1)+h[s]-h[x_1])+(w(x_1,x_2)+h[x_1]-h[x_2])+\cdots +(w(x_n,t)+h[x_n]-h[t])\\ & =w(s,x_1)+w(x_1,x_2)+\cdots +w(x_n,t)+h[s]-h[t]\\ & =dis(s,t)+h[s]-h[t]\end{array}$ 而$h[s]-h[t]$是只和起点终点有关，不会因此改变路径的权值和。 所以求出$di{s}^{\prime }(s,t)$之后，用 $dis(s,t)=di{s}^{\prime }(s,t)+h[t]-h[s]$就可以求出$dis(s,t)$了。 综上，Johnson步骤： 1、建立超级源点$x_0$,求其到各点最短路$h[N]$。 2、对所有边$(u,v)$,$w^{\prime }(u,v)=w(u,v)+h[u]-h[v]$。 3、Dijkstra求出$di{s}^{\prime }(u,v)$。 4、$dis(u,v)=di{s}^{\prime }(u,v)+h[v]-h[u]$。

代码：

模板题：洛谷P5905

#include<bits/stdc++.h> #define pii pair<int,int> #define int long long #define cl(x,y) memset(x,y,sizeof(x)) #define ct cerr<<"Time elapsed:"<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n"; #define mp make_pair #define pb push_back #define fi first #define se second #define all(x) x.begin(),x.end() #define lson x<<1,l,mid #define rson x<<1|1,mid+1,r #define INF 1e18 const int N=3e3+10; const int mod=1e9+7; const int inf=0x3f3f3f3f; const double eps=1e-8; const double pi=acos(-1); using namespace std; struct edge { int u,v,w; }e[N*3]; int n,head[N]={0},len=0,h[N],vis[N]={0},num[N]={0},dis[N]; void add(int u,int v,int w) { e[++len]={head[u],v,w}; head[u]=len; } int spfa() { int i; queue<int> q; for(i=0;i<=n;i++) h[i]=INF; h[0]=0; vis[0]=1; q.push(0); while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; for(i=head[u];i;i=e[i].u) { int v=e[i].v,w=e[i].w; if(h[v]>h[u]+w) { h[v]=h[u]+w; num[v]=num[u]+1; if(num[v]>=n+1) return 1; if(!vis[v]) { vis[v]=1; q.push(v); } } } } return 0; } void dij(int s) { int i; priority_queue<pii,vector<pii>,greater<pii>> q; for(i=1;i<=n;i++) { dis[i]=INF; vis[i]=0; } dis[s]=0; q.push(mp(0,s)); while(!q.empty()) { int u=q.top().se; q.pop(); if(vis[u]) continue; vis[u]=1; for(i=head[u];i;i=e[i].u) { int v=e[i].v,w=e[i].w; if(dis[v]>dis[u]+w) { dis[v]=dis[u]+w; if(!vis[v]) q.push(mp(dis[v],v)); } } } return; } void johnson() { int i,j; for(i=1;i<=n;i++) for(j=head[i];j;j=e[j].u) e[j].w+=h[i]-h[e[j].v]; for(i=1;i<=n;i++) { dij(i); int ans=0; for(j=1;j<=n;j++) if(dis[j]==INF) ans+=j*(int)(1e9); else ans+=j*(dis[j]+h[j]-h[i]); cout<<ans<<endl; } } signed main() { ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int m,i; cin>>n>>m; for(i=1;i<=m;i++) { int u,v,w; cin>>u>>v>>w; add(u,v,w); } for(i=1;i<=n;i++) add(0,i,0); if(spfa()) { cout<<-1<<endl; return 0; } johnson(); return 0; }