最短路问题在算法竞赛里几乎是一道“必点菜”不管你是刚摸到图论门槛的新手还是已经开始冲击省选、区域赛奖牌的选手都绕不开它。说白了最短路就是在带权图里找一条从起点到终点权值和最小的路径这个“权”可以是距离、时间、花费甚至是一道题里的跳跃次数。这篇文章想做的事很直接把从最基础的Dijkstra一直讲到最近讨论度很高的Johnson全源最短路再结合我自己刷过的题目、踩过的坑整理成一份可以照着学、照着练的完整路线。适合准备算法竞赛的学生、刚入行需要补图论基础的开发者以及所有想真正搞懂最短路本质的读者。很多初学者觉得最短路就是背个Dijkstra模板考试能默写就完事。但实际做题、做工程、参加比赛的时候你会发现负权边怎么处理、稠密图和稀疏图选哪个算法、全源最短路都有哪些解法、最短路怎么和DP、二分、分层图组合起来出题这些才是真正拉开差距的地方。这篇文章按照“入门到拓展”的顺序把整个知识体系、个人理解、题目推荐和调试经验全部串一遍。1. 最短路问题是什么为什么值得花力气学1.1 一句话讲清楚最短路问题给定一张带权图有向或无向每条边有一个权值最短路问题就是求从一个源点到某个目标点或者所有点的路径使得路径上所有边的权值之和最小。这个“权值”可以代表真实物理距离、交通时间、花费金额也可以代表某种抽象的代价。如果图上没有边权那问题退化为BFS求最短步数一旦带上权值问题就变得复杂有趣得多。你可能会问这有什么好学的不就是加权BFS吗问题在于图可以非常大——百万级别的点、千万级别的边——而算法竞赛和数据工程里都要求在秒级甚至毫秒级出结果。朴素的搜索会指数爆炸所以我们需要一系列经典算法在不同的条件下用不同的策略去逼近这个问题的解。这个“条件”包括边权是否为正、图是否稠密、是单源还是全源、是否要判负环。理解了这些条件你就理解了最短路算法家族的内部脉络。1.2 最短路能解决的现实问题最短路不只是一道刷题板子题工程里它的出场率非常高。地图导航是教科书级的例子滴滴打车、高德地图的路段规划本质上就是在实时图上跑带约束的最短路。通信网络里的路由协议比如OSPF、IS-IS用到的SPF算法就是Dijkstra的一个变种。CDN内容分发会计算用户到哪个节点最近最便宜这同样是全源最短路的一种应用。甚至在经济学里供应商成本最优链、供应链调运方案也经常建模成最短路问题来求解。我在实际项目中遇到过一类很典型的场景一个银行支付系统需要实时计算多币种之间的最优兑换路径汇率就是边权兑换方向就构成了一张有向图。因为存在间接兑换能拿到更优汇率的情况业务方本质上就是在求一个带手续费的最短路。这种时候如果你只会写Python里那个networkx的封装而不清楚底层在跑什么算法、负环怎么处理你是很难对结果做出正确判断的。1.3 最短路学习的整体路径规划根据我自己的学习经历和带过的新人经验最短路的学习应当分成四个台阶。第一台阶理解图的基本存储方式邻接矩阵、邻接表掌握Dijkstra堆优化和Bellman-Ford算法能处理单源最短路的基本题。第二台阶学会SPFA、理解松弛操作的本质能判断负环能处理带负权边的场景。第三台阶全源最短路掌握Floyd-Warshall和Johnson算法理解两者的适用边界。第四台阶最短路变形和进阶应用包括次短路、分层图、最短路DAG、差分约束等。这四个台阶并不是必须严格顺序执行的比如很多人学完Dijkstra直接去学Johnson跳过Floyd也能理解。但我的经验是Floyd虽然看似“笨重”它对动态规划思想——特别是“以中转点为中心递推”——的训练价值非常大不建议跳过去。Johnson算法本质上是在Floyd的“全源”目标和Dijkstra的“高效”之间做了一个极其聪明的桥接你不理解Dijkstra和Floyd就体会不到Johnson设计的精妙。1.4 需要具备的前置知识学最短路之前我建议你先确认自己掌握了这几样基本功。图论基础概念点、边、有向图、无向图、权值、路径、连通性这些不用多说了。图的存储邻接矩阵适合稠密图邻接表适合稀疏图竞赛里90%的最短路题都是用邻接表前向星或vector存边实现的。基础数据结构优先队列堆是Dijkstra堆优化的核心栈和队列是SPFA的基础建议先自己手写一遍或至少清楚priority_queue的底层逻辑。基础的DP概念最短路和DP的关系非常密切尤其是Floyd那一层接一层的状态转移本质上就是一种图上DP。这些前置知识不需要精通掌握到“能看懂代码、知道在干嘛”的程度就行。剩下最重要的其实就是耐心。最短路代码普遍不长但是“为什么这么写”“边界条件为什么这么设”里面藏着很多坑需要用题量去积累体感。2. 算法选型不同场景该用哪种最短路算法2.1 五种经典算法一张表看懂为了让你有一个全局视野我先把五种核心算法放在一起对比。这张表格我建议你反复看刷题遇到“不知道该用哪个算法”的时候回到这张表找答案比乱试模板高效得多。算法类型时间复杂度一般情况核心优势主要限制Dijkstra堆优化单源O((VE)logV)正权图最快最稳不能处理负权边Bellman-Ford单源O(VE)能处理负权边可判负环速度慢SPFA单源平均O(E)最坏O(VE)能处理负权边代码简单刻意构造数据可被卡死Floyd-Warshall全源O(V^3)代码极简支持负权边无负环只适合点数很小≤500左右Johnson全源O(V·E·logV)稀疏图全源最优支持负权边实现略复杂要先判负环2.2 正权图首选Dijkstra别犹豫只要确认了这张图里边权全部非负就用堆优化的Dijkstra没有第二种需要考虑的选项。理由很简单它是目前公认的、在单源最短路问题上综合表现最好的算法稳定不容易被卡模板熟了你甚至可以闭着眼睛写。它的问题只有“负权边”但题目若明确说明边权非负那它就是你唯一需要的主力算法。有些人可能会说“SPFA代码写起来短我习惯用SPFA”这在非负权图上是个坏习惯。SPFA的平均复杂度看着漂亮但出题人手里早就备好了专门卡SPFA的网格图、链式结构图一不小心就能把SPFA卡到指数级退化。我见过太多人在正权图上用SPFA被卡到TLE最后换回Dijkstra直接AC的案例。非负权图Dijkstra是最优解不需要犟。2.3 负权边出现时Bellman-Ford还是SPFA一旦题目里出现了负权边Dijkstra就失效了贪心选取最近点的前提被破坏。这时候你有两个选择Bellman-Ford和SPFA。Bellman-Ford的思路是纯暴力地做V-1轮松弛每一轮尝试对每条边进行“更新更短路径”的操作。它的时间复杂度是O(VE)在大图上会非常吃力但它的价值在于绝对稳定且天然支持负环检测——如果你在第V轮仍然有边能成功松弛就说明存在负环。而SPFA是对Bellman-Ford的队列优化只有被松弛过的节点才会进入队列下次有可能带动其他节点继续松弛。它代码短、常数小竞赛里更常用。我的建议是如果你在打比赛负权图优先写SPFA但心里要清楚它有被毒瘤数据卡到退化的风险所以需要优化SLF、LLL等同时要做好卡住后换Bellman-Ford甚至其他思路的心理准备。如果是在自己工程里用追求稳定的话就直接Bellman-Ford毕竟工程数据规模通常可控稳定性比极限速度更重要。SPFA和Bellman-Ford的负环检测方式其实是相通的记录每个节点的入队次数如果某个节点的入队次数超过了V次说明存在负环。2.4 全源最短路Floyd简单Johnson才是重头戏需要求任意两点间最短路时你面临两个方案。点数很少比如n300的时候直接Floyd三层循环代码简单到令人感动还能处理负权边只要没有负环。但是点数稍微大一点比如n10000边数m50000的图如果跑V次Dijkstra那是O(V·E·logV)的量级——这个复杂度不低但如果你仔细看它其实比Floyd的O(V^3)要好得多。Johnson全源最短路正是基于这个思路先用一次能处理负权边的算法比如Bellman-Ford/SPFA给每个节点算一个“势能”h再用势能重新赋权使得所有修改后的边权非负最后对每个点各跑一次Dijkstra。重新赋权后再通过势能差值还原原图的最短路长度。这个算法在稀疏图上做全源最短路时是综合性能最强的存在。这也是为什么最近它成了网络上的热门话题——因为很多人在做全源最短路题目时发现Floyd超时而逐个Dijkstra又可能被负权边卡住Johnson就是那个隐藏的最优解。3. 核心算法原理与手撕模板3.1 Dijkstra堆优化模板与实现要点如果你只能记住一个最短路算法那必须是堆优化的Dijkstra。它的核心思想是用贪心维护“当前确定最短路的点集S”每次从堆中弹出距离源点最近的点u尝试用它更新所有u出发能到达的点v。为什么这个算法要求边权非负因为一旦一个点被弹出堆并确认距离它的距离就永远不会再被更新——如果边权为负之后可能通过一条负边从别的点绕回来得到更小的距离贪心就被打破了。我给出一个可以当模板用的C写法#include bits/stdc.h using namespace std; const int maxn 1e5 5; struct Edge { int to, w; }; vectorEdge G[maxn]; long long dis[maxn]; int n, m, s; void dijkstra(int s) { memset(dis, 0x3f, sizeof dis); dis[s] 0; priority_queuepairlong long, int, vectorpairlong long, int, greaterpairlong long, int pq; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d ! dis[u]) continue; // 关键跳过过期节点 for (auto e : G[u]) { if (dis[e.to] dis[u] e.w) { dis[e.to] dis[u] e.w; pq.push({dis[e.to], e.to}); } } } }这里有两个细节我想多说一句。第一if (d ! dis[u]) continue这行看起来简单却能极大提升效率并避免逻辑错误。堆里同一个点可能会被push多次但只有最新一次push的距离才是有意义的旧记录直接跳过即可。第二dis数组初始化的INF值建议用0x3f3f3f3f因为它足够大而且0x3f3f3f3f 0x3f3f3f3f仍然在int范围内不会溢出——这个技巧对判重边、判多个条件时特别有用。3.2 Bellman-Ford与SPFA从松弛到判负环Bellman-Ford的原理是反复对所有边做松弛操作。松弛是什么对每条边u-v如果dis[u] w(u,v) dis[v]就更新dis[v]。一次完整的松弛遍历至少能让一条最短路径上的节点的距离“定下来”而一条简单最短路径最多经过V-1条边所以做V-1轮就一定得到最终答案。如果第V轮还能松弛说明存在一条可以从源点出发不断减小距离的负环。SPFA就是上面这个过程的队列版本。它的关键思想是只有被松弛过的节点才可能继续带动别人松弛所以用队列把待处理的节点装起来。代码如下void spfa(int s) { memset(dis, 0x3f, sizeof dis); memset(inq, 0, sizeof inq); dis[s] 0; q.push(s); inq[s] true; while (!q.empty()) { int u q.front(); q.pop(); inq[u] false; for (auto [v, w] : G[u]) { if (dis[v] dis[u] w) { dis[v] dis[u] w; if (!inq[v]) { q.push(v); inq[v] true; cnt[v]; } if (cnt[v] n) { /* 存在负环 */ } } } } }负环的判断用的是cnt[v] n也就是入队次数超过节点总数。这里有个坑如果源点根本到不了负环那负环是检测不出来的——必要时要建一个超级源点连接所有点或者对所有连通分量各跑一次SPFA。这在我后面讲“常见问题”时会再展开。3.3 Floyd的动态规划思路Floyd真的只有几行代码for (int k 1; k n; k) for (int i 1; i n; i) for (int j 1; j n; j) if (dis[i][j] dis[i][k] dis[k][j]) dis[i][j] dis[i][k] dis[k][j];但很多人背代码却没有理解为什么k循环在外层。这是最关键的dis[k][i][j]表示“经过编号前k个点作为中转站的情况下从i到j的最短路”。所以最外层循环必须枚举“允许使用的中转点集合”枚举的是状态阶段而不是路径长度。如果你把i和j放到外层本质上是错误的求出来的结果会很诡异。Floyd能处理负权边但不能有负环因为负环会让某些点对之间根本不存在最短路。想要同时判断负环也很简单跑完Floyd后检查dis[i][i]是否小于0即可——如果存在负环某个点绕一圈回到自身能让距离变成负的。3.4 Johnson全源最短路的完整走一遍Johnson算法经常被认为是“考场上不常用”的进阶算法但它其实是全源最短路里最优雅的解法之一尤其是当图的点数较大、边数不太多的稀疏图场景。完整步骤分为三步。第一步从超级源点0连一条权值为0的边到所有节点用Bellman-Ford或SPFA跑一遍得到每个点的势能h[v]。这里的意义是h[v]表示从超级源点0到v的最短距离它是在允许负权边的情况下算出来的。第二步对每条边(u,v,w)重新赋权为w w h[u] - h[v]。这步操作的精妙之处在于新权值一定非负——因为三角形不等式保证h[v] h[u] w所以w 0。而且对于任意一条从起点s到终点t的路径重新赋权后的路径总长度相比原长度只增加了h[s] - h[t]这是常数偏移不会改变最短路径的结构只改变数值因此最后把结果减去偏移量就能还原真实最短距离。第三步对每个节点跑一遍Dijkstra得到任意两点间的最短路长度。我写一个Johnson的核心代码片段方便你体会整体结构void johnson() { // 1. 超级源点 0连向所有点权值为0的边 // 2. SPFA跑一次得到 h[i] for (int i 1; i n; i) G[0].push_back({i, 0}); spfa(0); // 算出 h[] // 3. 重新赋权非负 for (int u 1; u n; u) for (auto e : G[u]) e.w h[u] - h[e.to]; // 4. 对每个点各跑一次Dijkstra for (int s 1; s n; s) dijkstra(s); }理解这个算法的关键点是为什么能保证跑完SPFA后所有边的新权值非负我建议你拿一张带负权边的图自己手推一遍。我把三角形不等式写出来你就立刻懂了因为h[v]是源点到v的最短距离那么对任意边(u,v,w)必然满足h[v] h[u] w移项即得w h[u] - h[v] 0。就这么简单但第一次看到的时候真的是“啊哈”的感觉。Johnson的时间复杂度是O(V·E·logV)在稀疏图上几乎是全源最短路的最佳选择在稠密图上Floyd的O(V^3)可能更划算。所以选型时先看图的密度再决定算法而不是只看“能不能用”。4. 题目推荐从入门到拓展的分级刷题建议4.1 入门级题目约30-60分钟可做如果你刚学完Dijkstra模板我建议用下面这几道题来练手感。洛谷P3371是最经典的“单源最短路径弱化版”数据范围很小主要用来验证模板对不对、会不会RE、会不会忘了初始化。洛谷P4779是“单源最短路径标准版”同样的题面但数据范围拉到n≤1e5、m≤2e5这时候就必须用堆优化Dijkstra了拿SPFA硬写大概率TLE。这两道题合在一起能让你强制感受到算法选型带来的性能差距。我还想推荐AcWing 849和850的Dijkstra系列题它的输入数据很规整适合拿来对比朴素版和堆优化版的差异。入门阶段做题不需要贪多一天两道就够关键是把模板写到“40秒内能敲完并且一遍过”的手感出来。4.2 进阶必刷题目经典模型进阶阶段的核心是“从会背模板到会分析题目”。负权边与负环判定的代表题是洛谷P3385负环必须用SPFA或Bellman-Ford写还要处理“从源点不可达的负环”这个陷阱。次短路入门是洛谷P2865它要求你求严格次短路一个常见思路是同时维护最短路和次短路两个dis数组但要注意次短路更新时不能直接清掉最短路的状态细节不少。分层图最短路推荐洛谷P4568这是经典中的经典。它的思路是把图复制成k1层层与层之间有“跳到下一层”的特殊零权边然后跑从起点到任意层终点的最短路。我记得第一次做这道题的时候代码写了两百多行后来理解了“分层图 扩维状态”的本质后用带维度的Dijkstra写代码量直接砍半跑得还更快。这就是模型抽象能力带来的提升。4.3 拓展拔高题目变形与综合到拓展阶段我强烈推荐刷这几道题**Codeforces 1320DReachable Strings**虽然表面是字符串题但本质上用到的是奇偶位置上的走法计数与图上最短路思维有共通之处。**洛谷P1144最短路计数**要求你在求最短路的同时统计路径条数这需要理解Dijkstra松弛过程中更新和相等两种情况的分别处理对状态的理解帮助巨大。POJ 1062昂贵的聘礼是一道带限制条件的最短路题题面很有味道核心是把“等级限制”转换为枚举可行区间在区间内跑最短路。这种“约束最短路”的组合完全就是竞赛题里的家常便饭。如果你想挑战Johnson全源最短路我推荐Codeforces 567EPresident and Roads虽然不是直接的Johnson裸题但考察了“一条边是否可能出现在最短路中”的判断需要结合最短路DAG和正向反向Dijkstra来思考。还有洛谷P5903这种需要实现树上的最近公共祖先与最短路综合应用的题目也可以作为压轴训练。4.4 刷题策略怎么刷效率最高刷题最忌讳的是“看一道抄一次模板过一道忘一道”。我自己常用的策略是循环刷题法第一遍每天挑2-3道同一主题的题当场AC不算完必须独立手写一遍第二遍隔一周再刷同样几道题追求不看模板一写就过第三遍把所有题目当作复习卷只列思路不敲代码快速检验自己能否在30秒内判断出算法类型。三轮下来一个知识点的掌握度比盲目刷50道新题高得多。另外我强烈建议准备一个“最短路错题本”。不需要记完整代码只记三行错误现象、错误原因、以后怎么避免。比如“TLE原因稠密图用了朴素Dijkstra应该用堆优化或邻接表优化教训先看数据范围再选算法”。这种短记录积累到十页之后你的水平一定会有质的飞跃。5. 踩坑记录与调试心得5.1 最短路代码最常见的五个坑先说我最常遇到的坑希望你别踩。第一个坑重边没处理。题目说“两点之间可能有多条边”你直接存边不比较结果Dijkstra从堆里弹出的时候总拿短的更新然后用长的把稍长的更新了导致结果偏大。解决方案是存图时直接对重边取min或者用邻接矩阵的时候就取min邻接表的话在输入时就处理。第二个坑数组开小。存边数组如果按题目给的m开但反向边加了一次经常会把数组越界卡到诡异的RE。我在洛谷P4779上就经历过一次看着AcWing上一模一样的代码就是RE最后发现是结构体数组开少了一半。稳妥做法是所有边数组开到2倍m再加5永远是安全的。第三个坑起点不可达的节点距离是INF。很多题目问“如果不到输出-1”你判断INF时要用 INF/2而不是 INF因为路径计算中INF经过加法后会变成更大的数。第四个坑long long问题。点数和边权乘起来如果可能超过int范围距离数组就必须开long long不然会在极端数据点WA到怀疑人生。第五个坑priority_queue的pair排序。如果你用pairint,int存(距离,节点号)对下表是second不是first。我见过好几个新手把节点号放first导致结果完全错乱。5.2 数据范围与INF设置INF设置是一门小学问。我推荐0x3f3f3f3f而不是INT_MAX原因有三第一这个值约等于1e9足够大大于普通题目中任何可能的最短路长度第二0x3f3f3f3f加上自身后仍然在int范围内不会溢出变成负数第三memset对0x3f3f3f3f有专门的字节填充优化一行memset(dis, 0x3f, sizeof dis)就能把所有元素都初始化成同一个值非常方便。如果你的距离数组是long long那INF就用0x3f3f3f3f3f3f3f3f同时记得memset的第二个参数还是0x3f这是因为memset是按字节填的long long的8个字节全填0x3f得到的值正好就是0x3f3f3f3f3f3f3f3f。这背后的原理很简单但不懂的话用memset初始化long long数组时很容易写出错误代码。5.3 重边、自环与邻接表数组大小的坑自环在多数最短路题里可以直接忽略因为从u绕回u不可能比直接从u出发更短除非是负权自环那就要小心负环判断。重边则必须处理。比如Test Sample中两个点之间有3条边权值分别是1、5、2你不处理就存3条边跑出来的结果依然是1但处理了取最小值能减少边的数量常数优化是有实际价值的——在大规模图上减少重复的松弛操作有时候能提速30%以上。邻接表数组大小的问题我再强调一遍如果用链式前向星head数组开n1to/next/w数组至少开2m5无向图如果题目加了额外边或者分层图建议直接开到4m5。这是用血的教训换来的经验。为什么是4倍因为分层图需要复制k份原图如果你把k算错了数组开小了跑起来就是一个极其难查的越界RE。为了防止这个坑我现在写代码习惯先把所有数组开成一个足够大的常量倍数等AC了再优化空间。5.4 实测Debug技巧最短路题Debug有几个非常好用的手段。第一招小数据对拍。自己写一个暴力Floyd或者BFS然后用随机小图生成器疯狂对拍一旦跑出不一致就打印出来逐步比对。第二招打印dist数组。在关键节点处输出dis值看看哪一步更新出了问题是初始值错了还是更新条件写反了。第三招给每条边编号调试。如果你怀疑是重边或者边的顺序问题打印松弛过的边的编号十有八九能立刻定位。我也建议你养成分步测试的习惯先把Dijkstra模板跑通sample再逐步加负权边处理、加记录方案、加分层图、加计数。不要一次性写完几百行再调那会非常痛苦。我记得有一次写分层图Dijkstra因为把一个“跳到下一层”的边权从0写成了1整个样例都对了但额外构造的数据全挂排查了一个多小时最后就是一个小数字的错。这些看起来不起眼的细节往往就是最短路代码最磨人的地方。6. 从最短路走向更广阔的图论世界6.1 最短路DAG与DP很多最短路题目不只是让你输出距离值还要求你统计最短路径条数、输出最短路径方案、或者基于最短路DAG做进一步DP。最短路DAG是什么当你跑完一遍单源最短路后保留所有满足“dis[u] w dis[v]”的边这些边就构成一张有向无环图因为最短路不可能形成环。这张DAG上可以做很多事最短路计数、关键边判断、必经点判断等等。从实际做题角度看建出最短路径DAG之后很多问题都会变得清晰很多。比如“求最短路上有多少种不同的走法”你只需要在DAG上做拓扑序DP即可比如“问一条边是否一定在最短路上”只需要分别从源点s和终点t跑两次最短路然后判断该边的两个端点是否满足“s到u的最短路 w v到t的最短路 s到t的最短路”。这种思维是很多难题的基础必须掌握。6.2 差分约束系统差分约束系统是最短路的一个经典应用很多选手学到这个知识点的时候会有“原来如此”的感觉。它的核心是一堆形如x_i - x_j c的不等式可以抽象成一条从j到i权值为c的边然后跑最短路来判断所有不等式能否同时成立。如果存在负环说明不等式组无解如果不存在负环跑出来的距离就是一组可行解。这里有一个很有意思的转化求x的最大值用最短路求x的最小值用最长路。最长路实现起来可以取负的边权跑最短路也可以直接把Dijkstra换成SPFA改判断条件。我在刷POJ 3169Layout牛围栏的时候被这个建模卡了很久后来意识到“差分约束 不等式转图 负环判断”之后这类题就是一马平川。强烈建议你找3道差分约束题专项训练能极大加深你对最短路本质的理解。6.3 分层图最短路分层图我前面提到过是竞赛里一个极其高频的考点。它的思想非常直观当题目中有K次“特殊操作”的时候比如可以免费走K条边、可以跳过K次红绿灯把图复制成K1层第i层表示“已经使用了i次特殊操作”的状态层间特殊边的权值为0层内普通边照常连接。然后在扩展后的状态图上跑最短路。这个模型看似简单但很多题目会隐藏“必须在某一层才能做某事”的约束比如“免费边必须在到达终点前恰好用完K次”“某些点只能在特定层访问”等等。这些约束就需要你灵活设计层间边的方向和权值。做题时我建议把状态图先画出来再写代码不然层数和编号很容易搅成一团。6.4 Johnson算法的深层价值为什么Johnson算法值得你专门花时间研究因为它不仅是全源最短路的工具更深层的是它展示了通过重新赋权把负权图转化为非负权图这样一种通用技巧。同样的思想在很多其他问题里也会出现比如差分约束中把不等式化成边、费用流中的势能优化、KM算法中顶标的维护都能看到“给点设定一个势能用来修正边权”的影子。从实用主义的角度看Johnson算法在稀疏图上做全源最短路几乎是无敌的你不需要O(n^3)的Floyd也不需要担心跑V次Bellman-Ford太慢只需要一次SPFA加上V次Dijkstra配合堆优化综合性能非常好。如果你所在研发团队需要在稀疏图上频繁查询任意两点最短路Johnson的思路可以直接用来做离线预处理把每次查询降到O(1)。我自己的学习体会是最短路这个坑挖下去真的是深不见底从Dijkstra一路学到Johnson从单源走到全源从单纯求距离到结合计数、方案、DP、约束建模每一步都在加深你对图和动态规划的理解。希望你拿着这份从入门到拓展的整理少踩我踩过的坑多尝到AC的快感。 
长河君 · 2026/10/11 4:59:24 · 阅读 1.2k 最短路算法全解析：从Dijkstra到Johnson的进阶路线
最短路问题在算法竞赛里几乎是一道“必点菜”不管你是刚摸到图论门槛的新手还是已经开始冲击省选、区域赛奖牌的选手都绕不开它。说白了最短路就是在带权图里找一条从起点到终点权值和最小的路径这个“权”可以是距离、时间、花费甚至是一道题里的跳跃次数。这篇文章想做的事很直接把从最基础的Dijkstra一直讲到最近讨论度很高的Johnson全源最短路再结合我自己刷过的题目、踩过的坑整理成一份可以照着学、照着练的完整路线。适合准备算法竞赛的学生、刚入行需要补图论基础的开发者以及所有想真正搞懂最短路本质的读者。很多初学者觉得最短路就是背个Dijkstra模板考试能默写就完事。但实际做题、做工程、参加比赛的时候你会发现负权边怎么处理、稠密图和稀疏图选哪个算法、全源最短路都有哪些解法、最短路怎么和DP、二分、分层图组合起来出题这些才是真正拉开差距的地方。这篇文章按照“入门到拓展”的顺序把整个知识体系、个人理解、题目推荐和调试经验全部串一遍。1. 最短路问题是什么为什么值得花力气学1.1 一句话讲清楚最短路问题给定一张带权图有向或无向每条边有一个权值最短路问题就是求从一个源点到某个目标点或者所有点的路径使得路径上所有边的权值之和最小。这个“权值”可以代表真实物理距离、交通时间、花费金额也可以代表某种抽象的代价。如果图上没有边权那问题退化为BFS求最短步数一旦带上权值问题就变得复杂有趣得多。你可能会问这有什么好学的不就是加权BFS吗问题在于图可以非常大——百万级别的点、千万级别的边——而算法竞赛和数据工程里都要求在秒级甚至毫秒级出结果。朴素的搜索会指数爆炸所以我们需要一系列经典算法在不同的条件下用不同的策略去逼近这个问题的解。这个“条件”包括边权是否为正、图是否稠密、是单源还是全源、是否要判负环。理解了这些条件你就理解了最短路算法家族的内部脉络。1.2 最短路能解决的现实问题最短路不只是一道刷题板子题工程里它的出场率非常高。地图导航是教科书级的例子滴滴打车、高德地图的路段规划本质上就是在实时图上跑带约束的最短路。通信网络里的路由协议比如OSPF、IS-IS用到的SPF算法就是Dijkstra的一个变种。CDN内容分发会计算用户到哪个节点最近最便宜这同样是全源最短路的一种应用。甚至在经济学里供应商成本最优链、供应链调运方案也经常建模成最短路问题来求解。我在实际项目中遇到过一类很典型的场景一个银行支付系统需要实时计算多币种之间的最优兑换路径汇率就是边权兑换方向就构成了一张有向图。因为存在间接兑换能拿到更优汇率的情况业务方本质上就是在求一个带手续费的最短路。这种时候如果你只会写Python里那个networkx的封装而不清楚底层在跑什么算法、负环怎么处理你是很难对结果做出正确判断的。1.3 最短路学习的整体路径规划根据我自己的学习经历和带过的新人经验最短路的学习应当分成四个台阶。第一台阶理解图的基本存储方式邻接矩阵、邻接表掌握Dijkstra堆优化和Bellman-Ford算法能处理单源最短路的基本题。第二台阶学会SPFA、理解松弛操作的本质能判断负环能处理带负权边的场景。第三台阶全源最短路掌握Floyd-Warshall和Johnson算法理解两者的适用边界。第四台阶最短路变形和进阶应用包括次短路、分层图、最短路DAG、差分约束等。这四个台阶并不是必须严格顺序执行的比如很多人学完Dijkstra直接去学Johnson跳过Floyd也能理解。但我的经验是Floyd虽然看似“笨重”它对动态规划思想——特别是“以中转点为中心递推”——的训练价值非常大不建议跳过去。Johnson算法本质上是在Floyd的“全源”目标和Dijkstra的“高效”之间做了一个极其聪明的桥接你不理解Dijkstra和Floyd就体会不到Johnson设计的精妙。1.4 需要具备的前置知识学最短路之前我建议你先确认自己掌握了这几样基本功。图论基础概念点、边、有向图、无向图、权值、路径、连通性这些不用多说了。图的存储邻接矩阵适合稠密图邻接表适合稀疏图竞赛里90%的最短路题都是用邻接表前向星或vector存边实现的。基础数据结构优先队列堆是Dijkstra堆优化的核心栈和队列是SPFA的基础建议先自己手写一遍或至少清楚priority_queue的底层逻辑。基础的DP概念最短路和DP的关系非常密切尤其是Floyd那一层接一层的状态转移本质上就是一种图上DP。这些前置知识不需要精通掌握到“能看懂代码、知道在干嘛”的程度就行。剩下最重要的其实就是耐心。最短路代码普遍不长但是“为什么这么写”“边界条件为什么这么设”里面藏着很多坑需要用题量去积累体感。2. 算法选型不同场景该用哪种最短路算法2.1 五种经典算法一张表看懂为了让你有一个全局视野我先把五种核心算法放在一起对比。这张表格我建议你反复看刷题遇到“不知道该用哪个算法”的时候回到这张表找答案比乱试模板高效得多。算法类型时间复杂度一般情况核心优势主要限制Dijkstra堆优化单源O((VE)logV)正权图最快最稳不能处理负权边Bellman-Ford单源O(VE)能处理负权边可判负环速度慢SPFA单源平均O(E)最坏O(VE)能处理负权边代码简单刻意构造数据可被卡死Floyd-Warshall全源O(V^3)代码极简支持负权边无负环只适合点数很小≤500左右Johnson全源O(V·E·logV)稀疏图全源最优支持负权边实现略复杂要先判负环2.2 正权图首选Dijkstra别犹豫只要确认了这张图里边权全部非负就用堆优化的Dijkstra没有第二种需要考虑的选项。理由很简单它是目前公认的、在单源最短路问题上综合表现最好的算法稳定不容易被卡模板熟了你甚至可以闭着眼睛写。它的问题只有“负权边”但题目若明确说明边权非负那它就是你唯一需要的主力算法。有些人可能会说“SPFA代码写起来短我习惯用SPFA”这在非负权图上是个坏习惯。SPFA的平均复杂度看着漂亮但出题人手里早就备好了专门卡SPFA的网格图、链式结构图一不小心就能把SPFA卡到指数级退化。我见过太多人在正权图上用SPFA被卡到TLE最后换回Dijkstra直接AC的案例。非负权图Dijkstra是最优解不需要犟。2.3 负权边出现时Bellman-Ford还是SPFA一旦题目里出现了负权边Dijkstra就失效了贪心选取最近点的前提被破坏。这时候你有两个选择Bellman-Ford和SPFA。Bellman-Ford的思路是纯暴力地做V-1轮松弛每一轮尝试对每条边进行“更新更短路径”的操作。它的时间复杂度是O(VE)在大图上会非常吃力但它的价值在于绝对稳定且天然支持负环检测——如果你在第V轮仍然有边能成功松弛就说明存在负环。而SPFA是对Bellman-Ford的队列优化只有被松弛过的节点才会进入队列下次有可能带动其他节点继续松弛。它代码短、常数小竞赛里更常用。我的建议是如果你在打比赛负权图优先写SPFA但心里要清楚它有被毒瘤数据卡到退化的风险所以需要优化SLF、LLL等同时要做好卡住后换Bellman-Ford甚至其他思路的心理准备。如果是在自己工程里用追求稳定的话就直接Bellman-Ford毕竟工程数据规模通常可控稳定性比极限速度更重要。SPFA和Bellman-Ford的负环检测方式其实是相通的记录每个节点的入队次数如果某个节点的入队次数超过了V次说明存在负环。2.4 全源最短路Floyd简单Johnson才是重头戏需要求任意两点间最短路时你面临两个方案。点数很少比如n300的时候直接Floyd三层循环代码简单到令人感动还能处理负权边只要没有负环。但是点数稍微大一点比如n10000边数m50000的图如果跑V次Dijkstra那是O(V·E·logV)的量级——这个复杂度不低但如果你仔细看它其实比Floyd的O(V^3)要好得多。Johnson全源最短路正是基于这个思路先用一次能处理负权边的算法比如Bellman-Ford/SPFA给每个节点算一个“势能”h再用势能重新赋权使得所有修改后的边权非负最后对每个点各跑一次Dijkstra。重新赋权后再通过势能差值还原原图的最短路长度。这个算法在稀疏图上做全源最短路时是综合性能最强的存在。这也是为什么最近它成了网络上的热门话题——因为很多人在做全源最短路题目时发现Floyd超时而逐个Dijkstra又可能被负权边卡住Johnson就是那个隐藏的最优解。3. 核心算法原理与手撕模板3.1 Dijkstra堆优化模板与实现要点如果你只能记住一个最短路算法那必须是堆优化的Dijkstra。它的核心思想是用贪心维护“当前确定最短路的点集S”每次从堆中弹出距离源点最近的点u尝试用它更新所有u出发能到达的点v。为什么这个算法要求边权非负因为一旦一个点被弹出堆并确认距离它的距离就永远不会再被更新——如果边权为负之后可能通过一条负边从别的点绕回来得到更小的距离贪心就被打破了。我给出一个可以当模板用的C写法#include bits/stdc.h using namespace std; const int maxn 1e5 5; struct Edge { int to, w; }; vectorEdge G[maxn]; long long dis[maxn]; int n, m, s; void dijkstra(int s) { memset(dis, 0x3f, sizeof dis); dis[s] 0; priority_queuepairlong long, int, vectorpairlong long, int, greaterpairlong long, int pq; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d ! dis[u]) continue; // 关键跳过过期节点 for (auto e : G[u]) { if (dis[e.to] dis[u] e.w) { dis[e.to] dis[u] e.w; pq.push({dis[e.to], e.to}); } } } }这里有两个细节我想多说一句。第一if (d ! dis[u]) continue这行看起来简单却能极大提升效率并避免逻辑错误。堆里同一个点可能会被push多次但只有最新一次push的距离才是有意义的旧记录直接跳过即可。第二dis数组初始化的INF值建议用0x3f3f3f3f因为它足够大而且0x3f3f3f3f 0x3f3f3f3f仍然在int范围内不会溢出——这个技巧对判重边、判多个条件时特别有用。3.2 Bellman-Ford与SPFA从松弛到判负环Bellman-Ford的原理是反复对所有边做松弛操作。松弛是什么对每条边u-v如果dis[u] w(u,v) dis[v]就更新dis[v]。一次完整的松弛遍历至少能让一条最短路径上的节点的距离“定下来”而一条简单最短路径最多经过V-1条边所以做V-1轮就一定得到最终答案。如果第V轮还能松弛说明存在一条可以从源点出发不断减小距离的负环。SPFA就是上面这个过程的队列版本。它的关键思想是只有被松弛过的节点才可能继续带动别人松弛所以用队列把待处理的节点装起来。代码如下void spfa(int s) { memset(dis, 0x3f, sizeof dis); memset(inq, 0, sizeof inq); dis[s] 0; q.push(s); inq[s] true; while (!q.empty()) { int u q.front(); q.pop(); inq[u] false; for (auto [v, w] : G[u]) { if (dis[v] dis[u] w) { dis[v] dis[u] w; if (!inq[v]) { q.push(v); inq[v] true; cnt[v]; } if (cnt[v] n) { /* 存在负环 */ } } } } }负环的判断用的是cnt[v] n也就是入队次数超过节点总数。这里有个坑如果源点根本到不了负环那负环是检测不出来的——必要时要建一个超级源点连接所有点或者对所有连通分量各跑一次SPFA。这在我后面讲“常见问题”时会再展开。3.3 Floyd的动态规划思路Floyd真的只有几行代码for (int k 1; k n; k) for (int i 1; i n; i) for (int j 1; j n; j) if (dis[i][j] dis[i][k] dis[k][j]) dis[i][j] dis[i][k] dis[k][j];但很多人背代码却没有理解为什么k循环在外层。这是最关键的dis[k][i][j]表示“经过编号前k个点作为中转站的情况下从i到j的最短路”。所以最外层循环必须枚举“允许使用的中转点集合”枚举的是状态阶段而不是路径长度。如果你把i和j放到外层本质上是错误的求出来的结果会很诡异。Floyd能处理负权边但不能有负环因为负环会让某些点对之间根本不存在最短路。想要同时判断负环也很简单跑完Floyd后检查dis[i][i]是否小于0即可——如果存在负环某个点绕一圈回到自身能让距离变成负的。3.4 Johnson全源最短路的完整走一遍Johnson算法经常被认为是“考场上不常用”的进阶算法但它其实是全源最短路里最优雅的解法之一尤其是当图的点数较大、边数不太多的稀疏图场景。完整步骤分为三步。第一步从超级源点0连一条权值为0的边到所有节点用Bellman-Ford或SPFA跑一遍得到每个点的势能h[v]。这里的意义是h[v]表示从超级源点0到v的最短距离它是在允许负权边的情况下算出来的。第二步对每条边(u,v,w)重新赋权为w w h[u] - h[v]。这步操作的精妙之处在于新权值一定非负——因为三角形不等式保证h[v] h[u] w所以w 0。而且对于任意一条从起点s到终点t的路径重新赋权后的路径总长度相比原长度只增加了h[s] - h[t]这是常数偏移不会改变最短路径的结构只改变数值因此最后把结果减去偏移量就能还原真实最短距离。第三步对每个节点跑一遍Dijkstra得到任意两点间的最短路长度。我写一个Johnson的核心代码片段方便你体会整体结构void johnson() { // 1. 超级源点 0连向所有点权值为0的边 // 2. SPFA跑一次得到 h[i] for (int i 1; i n; i) G[0].push_back({i, 0}); spfa(0); // 算出 h[] // 3. 重新赋权非负 for (int u 1; u n; u) for (auto e : G[u]) e.w h[u] - h[e.to]; // 4. 对每个点各跑一次Dijkstra for (int s 1; s n; s) dijkstra(s); }理解这个算法的关键点是为什么能保证跑完SPFA后所有边的新权值非负我建议你拿一张带负权边的图自己手推一遍。我把三角形不等式写出来你就立刻懂了因为h[v]是源点到v的最短距离那么对任意边(u,v,w)必然满足h[v] h[u] w移项即得w h[u] - h[v] 0。就这么简单但第一次看到的时候真的是“啊哈”的感觉。Johnson的时间复杂度是O(V·E·logV)在稀疏图上几乎是全源最短路的最佳选择在稠密图上Floyd的O(V^3)可能更划算。所以选型时先看图的密度再决定算法而不是只看“能不能用”。4. 题目推荐从入门到拓展的分级刷题建议4.1 入门级题目约30-60分钟可做如果你刚学完Dijkstra模板我建议用下面这几道题来练手感。洛谷P3371是最经典的“单源最短路径弱化版”数据范围很小主要用来验证模板对不对、会不会RE、会不会忘了初始化。洛谷P4779是“单源最短路径标准版”同样的题面但数据范围拉到n≤1e5、m≤2e5这时候就必须用堆优化Dijkstra了拿SPFA硬写大概率TLE。这两道题合在一起能让你强制感受到算法选型带来的性能差距。我还想推荐AcWing 849和850的Dijkstra系列题它的输入数据很规整适合拿来对比朴素版和堆优化版的差异。入门阶段做题不需要贪多一天两道就够关键是把模板写到“40秒内能敲完并且一遍过”的手感出来。4.2 进阶必刷题目经典模型进阶阶段的核心是“从会背模板到会分析题目”。负权边与负环判定的代表题是洛谷P3385负环必须用SPFA或Bellman-Ford写还要处理“从源点不可达的负环”这个陷阱。次短路入门是洛谷P2865它要求你求严格次短路一个常见思路是同时维护最短路和次短路两个dis数组但要注意次短路更新时不能直接清掉最短路的状态细节不少。分层图最短路推荐洛谷P4568这是经典中的经典。它的思路是把图复制成k1层层与层之间有“跳到下一层”的特殊零权边然后跑从起点到任意层终点的最短路。我记得第一次做这道题的时候代码写了两百多行后来理解了“分层图 扩维状态”的本质后用带维度的Dijkstra写代码量直接砍半跑得还更快。这就是模型抽象能力带来的提升。4.3 拓展拔高题目变形与综合到拓展阶段我强烈推荐刷这几道题**Codeforces 1320DReachable Strings**虽然表面是字符串题但本质上用到的是奇偶位置上的走法计数与图上最短路思维有共通之处。**洛谷P1144最短路计数**要求你在求最短路的同时统计路径条数这需要理解Dijkstra松弛过程中更新和相等两种情况的分别处理对状态的理解帮助巨大。POJ 1062昂贵的聘礼是一道带限制条件的最短路题题面很有味道核心是把“等级限制”转换为枚举可行区间在区间内跑最短路。这种“约束最短路”的组合完全就是竞赛题里的家常便饭。如果你想挑战Johnson全源最短路我推荐Codeforces 567EPresident and Roads虽然不是直接的Johnson裸题但考察了“一条边是否可能出现在最短路中”的判断需要结合最短路DAG和正向反向Dijkstra来思考。还有洛谷P5903这种需要实现树上的最近公共祖先与最短路综合应用的题目也可以作为压轴训练。4.4 刷题策略怎么刷效率最高刷题最忌讳的是“看一道抄一次模板过一道忘一道”。我自己常用的策略是循环刷题法第一遍每天挑2-3道同一主题的题当场AC不算完必须独立手写一遍第二遍隔一周再刷同样几道题追求不看模板一写就过第三遍把所有题目当作复习卷只列思路不敲代码快速检验自己能否在30秒内判断出算法类型。三轮下来一个知识点的掌握度比盲目刷50道新题高得多。另外我强烈建议准备一个“最短路错题本”。不需要记完整代码只记三行错误现象、错误原因、以后怎么避免。比如“TLE原因稠密图用了朴素Dijkstra应该用堆优化或邻接表优化教训先看数据范围再选算法”。这种短记录积累到十页之后你的水平一定会有质的飞跃。5. 踩坑记录与调试心得5.1 最短路代码最常见的五个坑先说我最常遇到的坑希望你别踩。第一个坑重边没处理。题目说“两点之间可能有多条边”你直接存边不比较结果Dijkstra从堆里弹出的时候总拿短的更新然后用长的把稍长的更新了导致结果偏大。解决方案是存图时直接对重边取min或者用邻接矩阵的时候就取min邻接表的话在输入时就处理。第二个坑数组开小。存边数组如果按题目给的m开但反向边加了一次经常会把数组越界卡到诡异的RE。我在洛谷P4779上就经历过一次看着AcWing上一模一样的代码就是RE最后发现是结构体数组开少了一半。稳妥做法是所有边数组开到2倍m再加5永远是安全的。第三个坑起点不可达的节点距离是INF。很多题目问“如果不到输出-1”你判断INF时要用 INF/2而不是 INF因为路径计算中INF经过加法后会变成更大的数。第四个坑long long问题。点数和边权乘起来如果可能超过int范围距离数组就必须开long long不然会在极端数据点WA到怀疑人生。第五个坑priority_queue的pair排序。如果你用pairint,int存(距离,节点号)对下表是second不是first。我见过好几个新手把节点号放first导致结果完全错乱。5.2 数据范围与INF设置INF设置是一门小学问。我推荐0x3f3f3f3f而不是INT_MAX原因有三第一这个值约等于1e9足够大大于普通题目中任何可能的最短路长度第二0x3f3f3f3f加上自身后仍然在int范围内不会溢出变成负数第三memset对0x3f3f3f3f有专门的字节填充优化一行memset(dis, 0x3f, sizeof dis)就能把所有元素都初始化成同一个值非常方便。如果你的距离数组是long long那INF就用0x3f3f3f3f3f3f3f3f同时记得memset的第二个参数还是0x3f这是因为memset是按字节填的long long的8个字节全填0x3f得到的值正好就是0x3f3f3f3f3f3f3f3f。这背后的原理很简单但不懂的话用memset初始化long long数组时很容易写出错误代码。5.3 重边、自环与邻接表数组大小的坑自环在多数最短路题里可以直接忽略因为从u绕回u不可能比直接从u出发更短除非是负权自环那就要小心负环判断。重边则必须处理。比如Test Sample中两个点之间有3条边权值分别是1、5、2你不处理就存3条边跑出来的结果依然是1但处理了取最小值能减少边的数量常数优化是有实际价值的——在大规模图上减少重复的松弛操作有时候能提速30%以上。邻接表数组大小的问题我再强调一遍如果用链式前向星head数组开n1to/next/w数组至少开2m5无向图如果题目加了额外边或者分层图建议直接开到4m5。这是用血的教训换来的经验。为什么是4倍因为分层图需要复制k份原图如果你把k算错了数组开小了跑起来就是一个极其难查的越界RE。为了防止这个坑我现在写代码习惯先把所有数组开成一个足够大的常量倍数等AC了再优化空间。5.4 实测Debug技巧最短路题Debug有几个非常好用的手段。第一招小数据对拍。自己写一个暴力Floyd或者BFS然后用随机小图生成器疯狂对拍一旦跑出不一致就打印出来逐步比对。第二招打印dist数组。在关键节点处输出dis值看看哪一步更新出了问题是初始值错了还是更新条件写反了。第三招给每条边编号调试。如果你怀疑是重边或者边的顺序问题打印松弛过的边的编号十有八九能立刻定位。我也建议你养成分步测试的习惯先把Dijkstra模板跑通sample再逐步加负权边处理、加记录方案、加分层图、加计数。不要一次性写完几百行再调那会非常痛苦。我记得有一次写分层图Dijkstra因为把一个“跳到下一层”的边权从0写成了1整个样例都对了但额外构造的数据全挂排查了一个多小时最后就是一个小数字的错。这些看起来不起眼的细节往往就是最短路代码最磨人的地方。6. 从最短路走向更广阔的图论世界6.1 最短路DAG与DP很多最短路题目不只是让你输出距离值还要求你统计最短路径条数、输出最短路径方案、或者基于最短路DAG做进一步DP。最短路DAG是什么当你跑完一遍单源最短路后保留所有满足“dis[u] w dis[v]”的边这些边就构成一张有向无环图因为最短路不可能形成环。这张DAG上可以做很多事最短路计数、关键边判断、必经点判断等等。从实际做题角度看建出最短路径DAG之后很多问题都会变得清晰很多。比如“求最短路上有多少种不同的走法”你只需要在DAG上做拓扑序DP即可比如“问一条边是否一定在最短路上”只需要分别从源点s和终点t跑两次最短路然后判断该边的两个端点是否满足“s到u的最短路 w v到t的最短路 s到t的最短路”。这种思维是很多难题的基础必须掌握。6.2 差分约束系统差分约束系统是最短路的一个经典应用很多选手学到这个知识点的时候会有“原来如此”的感觉。它的核心是一堆形如x_i - x_j c的不等式可以抽象成一条从j到i权值为c的边然后跑最短路来判断所有不等式能否同时成立。如果存在负环说明不等式组无解如果不存在负环跑出来的距离就是一组可行解。这里有一个很有意思的转化求x的最大值用最短路求x的最小值用最长路。最长路实现起来可以取负的边权跑最短路也可以直接把Dijkstra换成SPFA改判断条件。我在刷POJ 3169Layout牛围栏的时候被这个建模卡了很久后来意识到“差分约束 不等式转图 负环判断”之后这类题就是一马平川。强烈建议你找3道差分约束题专项训练能极大加深你对最短路本质的理解。6.3 分层图最短路分层图我前面提到过是竞赛里一个极其高频的考点。它的思想非常直观当题目中有K次“特殊操作”的时候比如可以免费走K条边、可以跳过K次红绿灯把图复制成K1层第i层表示“已经使用了i次特殊操作”的状态层间特殊边的权值为0层内普通边照常连接。然后在扩展后的状态图上跑最短路。这个模型看似简单但很多题目会隐藏“必须在某一层才能做某事”的约束比如“免费边必须在到达终点前恰好用完K次”“某些点只能在特定层访问”等等。这些约束就需要你灵活设计层间边的方向和权值。做题时我建议把状态图先画出来再写代码不然层数和编号很容易搅成一团。6.4 Johnson算法的深层价值为什么Johnson算法值得你专门花时间研究因为它不仅是全源最短路的工具更深层的是它展示了通过重新赋权把负权图转化为非负权图这样一种通用技巧。同样的思想在很多其他问题里也会出现比如差分约束中把不等式化成边、费用流中的势能优化、KM算法中顶标的维护都能看到“给点设定一个势能用来修正边权”的影子。从实用主义的角度看Johnson算法在稀疏图上做全源最短路几乎是无敌的你不需要O(n^3)的Floyd也不需要担心跑V次Bellman-Ford太慢只需要一次SPFA加上V次Dijkstra配合堆优化综合性能非常好。如果你所在研发团队需要在稀疏图上频繁查询任意两点最短路Johnson的思路可以直接用来做离线预处理把每次查询降到O(1)。我自己的学习体会是最短路这个坑挖下去真的是深不见底从Dijkstra一路学到Johnson从单源走到全源从单纯求距离到结合计数、方案、DP、约束建模每一步都在加深你对图和动态规划的理解。希望你拿着这份从入门到拓展的整理少踩我踩过的坑多尝到AC的快感。