当前位置：首页 > news >正文

全源最短路问题

news 2026/7/26 4:40:14

全源最短路问题

0xFF 引入

上回讲了单源最短路可有许多问题没有给出起点这可怎么办呢?

0x01 Floyd-Warshall

问题

Floyd-Warshall 简称 Floyd 又叫插点法其实本质上是 dp

$dp_{i,j,k} $ 表述从 $i$ 到 $j$ 经过 $k$ 的最短路长度

状态说完了接下来是边界可以发现 $dp_{i,j,0}=(i,j)$

最后就是状态转移方程了

\[dp_{i,j,k}=\min(dp_{i,j,k-1},dp_{i,k,k-1}+dp_{k,j,k-1}) \]

刷过题的都看的出来可以用滚动数组来优化掉第三维

\[dp_{i,j}=\min(dp_{i,j},dp_{i,k}+dp_{k,j}) \]

这样我们就发明出了 Floyd 算法

code:

//LG
//【模板】Floyd
//https://www.luogu.com.cn/problem/B3647
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll G[110][110];
ll dp[110][110];
int n,m;
int main(){cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dp[i][j]=G[i][j]=(i==j?0:INT_MAX);while(m--){int u,v;ll w;cin>>u>>v>>w;dp[u][v]=G[u][v]=min(G[u][v],w);dp[v][u]=G[v][u]=min(G[v][u],w);}for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);}}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cout<<dp[i][j]<<" ";}cout<<"\n";}return 0;
}

注意


这里的 k 是阶段所以一定要在最外层

0x02 Johnson

现在的你:

这也太简单了吧

那请看题

好你马上打了个 Floyd 等等...

$n \le 3 \times 10^3$ 那 Floyd 就大约要 $27000000000$ 根据 1秒 1e6 1兆1e5 那要 $27s$

那跑 $n$ 次 Dijkstra ?

有负权

啊啊啊

聪明的你一定会想到这种方法

那就是给每条边加上一个大的数

好吧这是错的

因为你的边越多加的数就越多

那要怎么做呢?

0x01 $h$ 数组势能数组

我们可以建造一个 超级源点 比如 $0$ 接下来以 超级源点 作为 $s$ 跑一遍 SPFA 同时判断是否有负环同时把这次的最短路记为 $h$ 我们把它叫做 势能数组

0x02 重新建图

接下来我们把 $(u,v)+h_u-h_v$ 当做新的 $(u,v)$

然后做 $n$ 次 Dijkstra 如果第 $i$ 次 $v$ 的最短路是 $l_v$ 那真正的最短路就是 $l_v-h_i+h_v$

code:

//LG
//【模板】全源最短路（Johnson）
//https://www.luogu.com.cn/problem/P5905
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
struct e{int u,v;ll w;
};
vector<e> G[3010];
vector<e> nG[3010];
int n,m;
vector<ll> h;
bool SPFA(){h[0]=0;vector<int> cnt(n+10,0);vector<bool> f(n+10,1);f[0]=0;queue<int> q;q.push(0);while(q.size()){int u=q.front();q.pop();f[u]=1;for(int i=0;i<G[u].size();i++){int v=G[u][i].v;ll w=G[u][i].w;if(h[v]>h[u]+w){cnt[v]=cnt[u]+1;if(f[v])q.push(v);h[v]=h[u]+w;}if(cnt[v]>n)return 0;}}return 1;
}
ll Dijkstra(int s){vector<ll> l(n+10,1e9);l[s]=0;vector<bool> f(n+10,1);priority_queue<pair<ll,int> > q;q.push(make_pair(0,s));while(q.size()){int u=q.top().second;q.pop();if(f[u]){f[u]=0;for(int i=0;i<nG[u].size();i++){int v=nG[u][i].v;ll w=nG[u][i].w;if(l[v]>l[u]+w){l[v]=l[u]+w;q.push(make_pair(-l[v],v));}}}}ll ans=0;for(ll i=1;i<=n;i++){if(f[i])ans+=i*1000000000;else ans+=i*(l[i]-h[s]+h[i]);}return ans;
}
void Johnson(){for(int i=1;i<=n+10;i++)h.push_back(1e9);for(int i=1;i<=n;i++)G[0].push_back({0,i,0});if(SPFA()==0){cout<<-1;}else{for(int i=1;i<=n;i++){for(int j=0;j<G[i].size();j++){int u=i,v=G[i][j].v;ll w=G[i][j].w+h[u]-h[v];nG[u].push_back({u,v,w});}}for(int i=1;i<=n;i++)cout<<Dijkstra(i)<<"\n";}
}
ll g[3010][3010];
int main(){cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)g[i][j]=(i!=j?1e9:0);while(m--){int u,v;ll w;cin>>u>>v>>w;g[u][v]=min(g[u][v],w);}for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(g[i][j]!=1e9)G[i].push_back({i,j,g[i][j]});Johnson();return 0;
}