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

朱世乐的 Johnson 算法笔记

  1. 这个算法的使命是啥?
    解决“全源最短路”问题(所有点到所有点的最短路)。
    特别擅长处理带负权边的稀疏图。是对“跑N遍SPFA”的巨大优化。
  2. 核心思想?(天才的魔法)
    Dijkstra 很快,但怕负权边。
    Johnson 的想法:施展一个魔法,把所有边权都变成正数,然后就可以开心地跑 N 遍 Dijkstra 了!
  3. 魔法怎么施展?(三步走)
    第一步:【前处理】跑 SPFA 算“势能h”
    目的:找到一组“修正值”h[i],并且顺便检查有没有负环。
    做法:
    新建一个“超级源点” S (比如 n+1 号点)。
    从 S 向所有其他点 i 连一条权重为 0 的边。
    从 S 开始,跑一遍 SPFA。
    如果SPFA报告有负环,整个图无解,输出 -1。
    如果没有负环,SPFA算出的从S到每个点i的距离 dist[i],就是我们的魔法修正值 h[i]。
    第二步:【核心】跑 N 遍 Dijkstra
    目的:在新图上,快速计算出所有点对的“魔法距离”。
    做法:
    根据公式 w_new = w_old + h[u] - h[v],创建一张新图 g_new。这张新图里所有边权都是正的!
    然后,就是你最熟悉的操作了:写一个 for 循环,从 s = 1 到 n,以每个点为起点,在 g_new 上跑一遍你的 Dijkstra 模板。
    跑完后,得到的是“魔法距离” dist[s][j]。
    第三步:【后处理】还原真实距离
    目的:把“魔法距离”变回我们想要的真实距离。
    做法:
    套用公式:real_dist = magic_dist - h[起点] + h[终点]。
    dist_real[s][j] = dist[s][j] - h[s] + h[j]。
  4. 要注意的“坑”:
    不连通:如果SPFA跑完后,某个点的 h[i] 还是无穷大,说明超级源点到不了它,要特殊处理。
    INF 值:注意题目对“无穷大”的定义,输出时要统一。
    数据类型:路径和可能很大,记得用 long long

代码:

include<bits/stdc++.h>

using namespace std;
using ll=long long;
const ll INF=1e18;
bool spfa(int s,int n,const vector<vector<pair<int,int>>>&g,vector&h){
h.assign(n+1,INF);
vectorcnt(n+1,0);
queueq;
vectorinqueue(n+1,false);
h[s]=0;
q.push(s);
inqueue[s]=true;
while(!q.empty()){
int u=q.front();
q.pop();
inqueue[u]=false;
for(auto const& [v,w]:g[u]){
if(h[u]!=INF&&h[u]+w<h[v]){
h[v]=h[u]+w;
if(!inqueue[v]){
q.push(v);
inqueue[v]=true;
cnt[v]++;
if(cnt[v]>n){
return false;
}
}
}
}
}
return true;
}
void solve(){
int n,m;
cin>>n>>m;
// vector<vector<pair<int,int>>>g(n+1);
vector<tuple<int,int,int>>edges;
for(int i=0;i<m;i++){
int u,v,w;
cin>>u>>v>>w;
// g[u].push_back({v,w});
edges.emplace_back(u,v,w);
}
vector<vector<pair<int,int>>>g_spfa(n+2);
for(const auto&edge:edges){
g_spfa[get<0>(edge)].push_back({get<1>(edge),get<2>(edge)});
}
int ss=n+1;
for(int i=1;i<=n;i++){
g_spfa[ss].push_back({i,0});
}
vectorh;
if(!spfa(ss, n + 1, g_spfa, h)){
cout<<"-1"<<"\n";
return ;
}
vector<vector<pair<int,int>>>new_g(n+1);
for(const auto&edge:edges){
int u,v,w;
tie(u,v,w)=edge;
if(h[u]!=INF && h[v]!=INF){
new_g[u].push_back({v, w + (int)h[u] - (int)h[v]});
}
}
for (int s = 1; s <= n; s++) {
vector dist(n+1, INF);
vector vis(n+1, false);
dist[s] = 0;
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>>pq;
pq.push({0, s});

    while(!pq.empty()){auto[d,u]=pq.top();pq.pop();if(vis[u]) continue;vis[u]=1;for(auto const& [v,w]:new_g[u]){ if(dist[u] != INF && dist[u]+w<dist[v]){ dist[v]=dist[u]+w;pq.push({dist[v],v});}}}ll ans = 0;for(int j=1; j<=n; j++){if(h[s]==INF || dist[j]==INF){ans += (ll)j * 1000000000LL; }else{ll tmp = dist[j] - h[s] + h[j];ans += (ll)j * tmp;}}cout << ans << "\n";
}

}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}

http://www.hskmm.com/?act=detail&tid=30286

相关文章:

  • day010
  • 20232323 2025-2026-1《网络与系统攻防技术》实验一实验报告
  • 树莓派4B安装WiringPi使用gpio命令
  • 单调队列优化 dp
  • 1分钟Get宠物神兽壁纸我家猫被问疯了!
  • Zabbix 6.0+ 运用官方模板监控 Redis 数据库的完整安装指南
  • 【图论】Floyd算法简析
  • MyEclipse 2017 激活教程
  • 插入 dp
  • 05_Mysql与图片的存储
  • 【Linux】权限 - 实践
  • 斯坦福ACE框架:让AI自己学会写prompt,性能提升17%成本降87%
  • 【左扬精讲】SRE 别慌!我用 服务器监控指标 讲 KNN 分类算法,从相似度计算到异常识别,都是咱运维人能懂的话(含代码)
  • 博客园地址 - yuyue
  • 【终章】:幸福的复利——打造你的每日幸福微习惯 - 指南
  • 实用指南:Go 语言中的**数组 (Array)*用法
  • 行业词汇
  • Java实现业务数据报表的邮件定时发送功能
  • 编写Python自动化脚本,使用Autodesk Fusion辅助Ansys HFSS进行建模
  • 单 Pod DNS 记录(`web-0.nginx.default.svc.cluster.local`)排障与启用
  • 云原生周刊:KubeSphere社区版正式发布
  • 最好的感情
  • 三剑客系列-sed命令
  • 超景深立体显微镜厂家Top10推荐:拓界光电引领行业新风尚
  • 20232419 2025-2026-1《网络与系统攻防技术》实验一实验报告
  • 完整教程:用deepseek部署全自动的机器人--bytebot
  • 44. 开发商购买土地
  • 当AI与机器人走进生活:我们即将迎来的日常变革
  • 显微镜厂家TOP10推荐:拓界光电以创新技术引领精密观测新时代
  • net中使用了垃圾回收机制(GC)功能