很多刚开始刷洛谷图论模块的朋友看到最短路算法这个标签时第一反应是从起点DFS/BFS把所有能走的路线找一遍比一比哪个最小就行。实际上BFS只适用于所有边代价相同的情况。一旦边权变成了任意正整数、负数、或带有特殊含义的代价朴素的搜索会让状态数量爆炸。这时候需要的是Dijkstra、Bellman-Ford、SPFA、Floyd这一整套专门为最短路设计的方法。这篇博文会从问题本身讲起把从单源Dijkstra到多源Floyd的核心原理、模板代码、洛谷实战路线全部串一遍适合刚学完基础图论、准备刷最短路专题的读者也适合那些模板背了不少、但一遇到变式题就懵圈的朋友。1. 最短路到底在做什么先给问题一个准确画像1.1 一张图、一条路径、一个权值最短路问题在形式上的定义其实非常朴素给定一张带权图G(V,E)每条边有一个权值w给定一个起点s求s到每个点v的路径权值总和最小的那条路径。这里的权值在题里几乎可以是任何东西可以是公路里程、可以是被红绿灯耽误的时间、可以是转账的手续费、也可以是题目自己定义的一个代价函数。最短路算法不关心权值的物理含义它只关心一个抽象规则路径的总代价等于边权之和我们想求最小总和。这个抽象能力很重要。我见过不少同学看到一道题说从城市A到城市B最少要交多少过路费就不知道这是最短路了。实际上把过路费当作边权问题就原封不动变成了标准的最短路模型。1.2 无向图和有向图的差别无向图等价于双向边。如果题目说城市之间有一条道路你建图时要add(u,v,w)和add(v,u,w)各一次有向边则根据题意只加一条。方向性对最短路的正确性影响极大我见过很多新手在建图这步栽跟头——题目看懂了算法会写最后WA的原因居然是漏了反向边。这里建议养成两个习惯第一读入双向边时顺手写成两个add并且每次写完建图后先回看一眼第二如果题目要求从任意点出发回到某个终点这类往返路径大概率会用到反向建图技巧这个后面第5章会细说。1.3 什么时候不能直接BFSBFS求最短路成立的关键是第一次访问到某个点时用的步数一定是最小的。这在等权图中是显然的因为它按层数扩展。可一旦边上带了代价这一属性队列弹出的顺序就不再匹配代价从最小到最大的顺序。举个例子从起点到点A代价是100直接到点B代价是1但B到A只要1。用BFS会先访问A然后宣布我知道了到A是100实际上到A的最短代价明明只有2。BFS无法重估已经访问过的点这就是它不能处理带权图的根本原因。真正的最短路算法核心都是围绕松弛展开的。1.4 松弛最短路算法的心脏松弛relaxation这个名词看起来很学术其实意思就是如果经过某个中间点u能让s到v的当前最短距离变得更小那就更新它。写成代码就是if(dist[v] dist[u] w) dist[v] dist[u] w;。所有最短路算法本质上都在重复这一条语句只不过区别在于Dijkstra选择最信任的那个点去松弛Bellman-Ford把每条边一股脑松弛很多轮SPFA只让刚变小的点去松弛邻居Floyd则是让每一个点都尝试当中转。你把这个视角记在心里再去看后面的模板会轻松很多。2. Dijkstra堆优化单源最短路的绝对主角2.1 贪心思想与正权这个前提条件Dijkstra的思路一句话讲完维护dist数组每次在还没确定最短路的点里选一个当前dist最小的点把它标记为已确定然后用它去松弛所有出边。为什么当前dist最小的点可以直接确定为最终答案因为所有边权都是非负的。假设某个点的dist已经是从候选点里最小的了哪怕它之后真的还能再变短也必须有另一条从s出发、还没被选中的路径绕到它前面——而绕路会经过一个我们还没确定的点这条路的代价至少不小于当前这个最小dist不可能反而更小。这就是正权图给Dijkstra的免检证明。一旦出现负权边这个逻辑立刻失效一条路径可能先走一段很大的正权再被一条负权边大幅拉低贪心选出来的点随时可能后悔。所以如果你看到题里有负权边第一反应应该是Bellman-Ford/SPFA那一系而不是Dijkstra。2.2 邻接表、链式前向星怎么选先解决存储。n和m都比较小比如n100时邻接矩阵简单粗暴加边直接g[u][v]min(g[u][v],w)查询O(1)。但洛谷模板题n往往到1e5级别邻接矩阵O(n^2)内存直接爆掉必须用邻接表或链式前向星。邻接表(vectorvectorpairint,int)好写但常数稍大链式前向星是竞赛圈的经典写法效率高。我的建议是刷题阶段两者都练实际比赛用哪一种其实都可以关键是别建错方向。下面先给链式前向星的完整框架。const int N 100005; const int M 200005; struct Edge { int to, nxt, w; } e[M 1]; int head[N], tot; void init() { memset(head, -1, sizeof(head)); tot 0; } void addEdge(int u, int v, int w) { e[tot].to v; e[tot].w w; e[tot].nxt head[u]; head[u] tot; }注意M要开成边数的两倍双向边这是新手最常踩的坑数组开太小本地编译不报错提交直接RE。2.3 堆优化版本模板优先级队列到底在维护什么朴素Dijkstra每次要找最小dist点需要O(n)扫描堆优化就是用优先队列维护还没确定的点的最小dist把这一步降到O(log n)。整体复杂度O((nm)log n)处理1e5级别的图完全没问题。#include bits/stdc.h using namespace std; typedef long long ll; const ll INF 4e18; ll dist[N]; bool vis[N]; void dijkstra(int s) { fill(dist, dist N, INF); memset(vis, 0, sizeof(vis)); dist[s] 0; // 小根堆第一关键字是距离第二关键字是节点编号 priority_queuepairll, int, vectorpairll, int, greaterpairll, int pq; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (vis[u]) continue; vis[u] true; for (int i head[u]; i ! -1; i e[i].nxt) { int v e[i].to; if (dist[v] dist[u] e[i].w) { dist[v] dist[u] e[i].w; pq.push({dist[v], v}); } } } }这段代码里有几个细节需要解释为什么pq.top()取出后要判vis因为同一个点可能被重复push多次第一次弹出时它已经是最优的了后面再弹出的相同点直接跳过。为什么dist[v] dist[u] e[i].w而不是? 严格大于才会松弛等于的情况没必要再入队否则会用重复状态刷遍整张图白白浪费时间。优先队列是pairll,int默认大根堆必须加greater改成小根堆或者用结构体重载号。这个细节写错的话代码逻辑全对却会TLE。INF选4e18是因为long long范围内加法不会溢出如果习惯用0x3f3f3f3f那是int的常用值放到ll里加边权时可能溢出容易出诡异错误。2.4 重边与自环模板题里看不见的送分陷阱洛谷P4779这种模板题数据里重边是常客。链式前向星不处理重边读入时如果直接加边多条相同的u-v边都会留在图里松弛时会用较大权值先更新一次较小权值再更新一次结果仍然是正确的——只是多花点常数时间。但如果你想优化可以在读入时人为判断vector存图时用map记录已有边权并取min前向星版本偷懒不管也问题不大反正答案是对的。至于自环即u-u的边如果dist[u]w dist[u]恒成立w0时它对最短路没有任何影响Dijkstra里自然会被松弛条件过滤掉。所以模板题里重边不处理也能过真正需要小心的反而是后面要讲的Floyd因为Floyd用矩阵存储时如果不取min重边会造成错误。3. Bellman-Ford与SPFA负权场景的正确打开方式3.1 Bellman-Ford笨办法里的大道理Bellman-Ford的思路简单到像暴力把所有的边全部松弛一遍称为一轮重复n-1轮。为什么n-1轮就够了因为一条从起点到某点的最短路除非有负环否则最多只会包含n-1条边多了必然经过重复点有环而正权环或零权环都能拿掉不会让答案更差。每一轮松弛至少能让第k条边的最短路被确定下来所以n-1轮一定所有点都确定。这个算法复杂度O(n*m)数据一大就顶不住但它有两个价值第一能处理负权边第二它是理解SPFA和负环判定的基石。洛谷P3385这类题本质就是检测是否存在负环而不是真的让你求最短路值。3.2 SPFA谁在用队列给松弛加速SPFA全称是Shortest Path Faster Algorithm它是Bellman-Ford的队列优化。观察到一件事如果某个点u的dist这一轮根本没变那么用u去松弛它的邻居是毫无意义的因为邻居要更新的前提是u的当前dist变小了。所以SPFA维护一个队列只有dist发生变化的点才入队再用它去松弛邻居。平均情况下SPFA跑得飞快但它有一个致命弱点可以被特殊构造的数据卡成O(n*m)也就是比没优化还慢。这正是洛谷P4779标准版存在的意义之一——它明确把SPFA卡掉了迫使你去写堆优化Dijkstra。我的经验是正权图一律直接上Dijkstra堆优化别去赌SPFA数据不卡人SPFA只用在负权边或负环判定这种Dijkstra管不了的场景。3.3 负环判定模板负环存在意味着什么从某个点出发能绕一圈回到自己路径总和还是负数那么最短路的答案会是负无穷题目说存在最短路本身就不成立。SPFA判负环有两种写法我推荐记录每个点的最短路边数bool spfa(int s, int n) { fill(cnt, cnt N, 0); fill(dist, dist N, INF); vectorint inq(n, 0); queueint q; dist[s] 0; q.push(s); inq[s] 1; while (!q.empty()) { int u q.front(); q.pop(); inq[u] 0; for (int i head[u]; i ! -1; i e[i].nxt) { int v e[i].to; if (dist[v] dist[u] e[i].w) { dist[v] dist[u] e[i].w; cnt[v] cnt[u] 1; // 记录到v的最短路边数 if (cnt[v] n) return true; // 边数达到n说明有负环 if (!inq[v]) { q.push(v); inq[v] 1; } } } } return false; }这里cnt[v]cnt[u]1的含义是从s到v的当前最短路用了几条边。如果某条最短路用了大于等于n条边根据抽屉原理路径上一定经过了重复点存在一个环而环能让路径继续变短说明这是个负环。注意有些写法用入队次数n判断两种都可以但我个人更推荐记录边数因为它直接对应负环的经过n-1条边仍能再缩短的本质而且不容易在起点入队时误判。4. Floyd代码最短、思想最深的全体最短路4.1 多源最短路与所有中转点的思路Dijkstra求的是从一个源点出发到所有点的最短路要跑n次Dijkstra才能得到所有点对的最短路也就是O(n*(m log n))在图很大的时候根本跑不动。Floyd则用动态规划一次性解决所有点对代价是O(n^3)的时间复杂度所以它适用的图很小——洛谷的Floyd题基本都保证n500。n500时n^3是1.25亿次C在时限内勉强能过n1000就别碰Floyd。什么时候想到Floyd题目直接问任意两点间最短路或者数据范围极小让你一眼看出是O(n^3)能接受这两个信号出现时优先考虑它。这里有一个额外提醒Floyd虽然代码只有三行但在省选题里它经常作为某个大题的过渡工具出现直接考裸Floyd的题反而少更多需要你理解它的分阶段思想。4.2 状态设计与k必须在外层的原因Floyd的状态设计是f[k][i][j]表示在只允许使用前k个点作为中转点的条件下i到j的最短距离。转移方程有两部分不用第k个点中转那就是f[k-1][i][j]用第k个点中转则是f[k-1][i][k] f[k-1][k][j]取两者较小值。空间优化后只需要一个二维数组f[i][j]因为f[k]层只依赖f[k-1]层可以原地滚动。但三层循环的顺序必须是最外层枚举k中间枚举i内层枚举j。为什么k必须在最外层因为它代表的是阶段——你要先处理完只允许用1号点中转的情况才能处理允许用1、2号点中转的情况。如果把k放到最内层比如i-j-k的顺序那么更新f[i][j]时用到的f[i][k]、f[k][j]可能还是旧阶段的半成品算出来的结果当然不对。这个坑我当年踩过交上去WA看了好久才发现是循环顺序问题。4.3 Floyd模板与INF陷阱const ll INF 4e18; ll f[N][N]; // N 为点数上限 int n, m; void floyd() { for (int k 1; k n; k) for (int i 1; i n; i) { if (f[i][k] INF) continue; // 小优化去掉也能过 for (int j 1; j n; j) if (f[i][j] f[i][k] f[k][j]) f[i][j] f[i][k] f[k][j]; } }初始化要遵守三点f[i][i]0自己到自己距离是0其余位置初值INF读入边时f[u][v]min(f[u][v], w)无向边再加一条对称边。INF的选择在Floyd里是头等大事。如果用int的0x3f3f3f3f两个INF相加会溢出变成负值导致答案变成负数WA得莫名其妙。用long long配4e18两个INF相加也不会爆但判断不可达时不要用f[i][j]INF因为运算中INF可能被叠加成稍小一点的数稳妥写法是if(f[i][j] INF/2)视为不可达。4.4 Floyd的应用边界不只是暴力模板题很多题目看着不像求所有点对最短路实际上核心思想就是在动态规划里用Floyd式转移。洛谷P1119灾后重建就是个典型村庄被地震损坏后按时间顺序逐步修复每次修复一个点就询问当前条件下的一些点对最短路。这个题标准做法就是跑Floyd而且不是从头跑一遍而是利用Floyd的本质——修复第k个点时把k当中转点做一次完整的第k层转移即可。理解了Floyd的分阶段特性这道题就是个送分题。Floyd还有一个常见配套技巧把路径经过的权值限制在一张动态变化的图上每轮更新时用类似思想做转移。这个属于进阶内容本文不展开但希望你记住一点Floyd远不止一个三重循环模板它背后某个点作为中转的思想在很多DP题里都会反复出现。5. 建模能力才是分水岭从模板题到实战题5.1 一眼识别最短路题的套路经过模板训练后最难的其实是判断这道题该用什么算法。我根据自己的经验总结了一个判断顺序如果每条边的代价相同用BFS或01BFS就够如果代价不同且求的是单源点到所有点的最小总代价优先Dijkstra堆优化如果图里有负权边或者需要判断负环用SPFA/Bellman-Ford如果求的是所有点对的最短路、或者数据规模n很小500用Floyd如果需要记录具体路径或最短路径条数在跑最短路时额外维护pre数组或计数数组。第5点多说一句洛谷P1144最短路计数就是让你在跑最短路的同时统计有多少条最短路径。做法是在dist更新时同步更新计数数组松弛成功时cnt[v]cnt[u]遇到相等路径时cnt[v]cnt[u]。这个题很适合检验你对Dijkstra过程的理解而不是单纯背模板。5.2 洛谷最短路专题练习题单我可以给一份自己实践过、觉得难度递进合理的清单题号题目练习点P3371单源最短路径弱化版Dijkstra朴素模板练手P4779单源最短路径标准版堆优化Dijkstran到1e5P1339USACO热浪经典最短路应用题P1144最短路计数Dijkstra混合计数P1629邮递员送信反向建图求往返最短P3385负环模板SPFA负环判定P1119灾后重建Floyd分阶段运用P1346电车Floyd/最短路简单图论转换P1462通往奥格瑞玛的道路二分答案最短路综合顺序建议是先P3371、P4779把模板练到闭眼能默写再做P1339这种套壳题然后穿插P3385负环和P1119这种有思想含量的题。练完这个清单基本的最短路题你都能应对。P1462门槛高一些建议在二分答案专题学完后再回头做不要一上来就死磕。5.3 两个非常实用的建模技巧第一个是反向建图。比如一道题要你求其他所有点各自到终点t的最短路如果为每个起点都跑一次Dijkstra复杂度是O(n*m log n)很离谱。反过来把图的方向全部反转从t跑一次Dijkstra得到的就是所有点到t的最短路。这个技巧在P1629里体现得很典型邮递员要往返正向一次、反向一次两遍Dijkstra搞定。第二个是超级源点/超级汇点。题目问多个备选起点到某个终点的最短路最小值你可以在虚拟的0号节点向所有真实起点连权值为0的边把多源变成单源从0号节点跑一次Dijkstra就完成了。这个技巧在后续网络流、分层图题里也会用到顺手养成习惯能省很多时间。5.4 提交80分的通用排查清单网上一搜洛谷经常能看到这题为什么只拿80分明明本地样例过了之类的求助大部分情况不是思路错是下面某一条数组越界。M开小了或N和M上限搞混导致RE或玄学WA。建图方向错。有向边当无向边加或者漏了反向边。dist数组里的INF不够大。int用0x3f3f3f3f在加上边权后仍应保证不溢出但如果边权很大、多次相加可能溢出成负数导致错误路径被当成答案。重边处理。Floyd必须取minDijkstra前向星不取一般也能过但矩阵版必须取。多组数据未初始化。上一组测试数据遗留的head、dist、vis污染了下一组尤其是用vector存图时忘记clear。负环判断里的初始化位置。必须对每个起点都重新清空dist和cnt。遇到样例能过提交却错的时候别急着改算法。先写一个暴力程序比如DFS枚举路径、或者直接用Floyd在小图上验证随机造小数据对拍看是哪个点错了、错得多离谱通常很快就能定位到上面清单里的某一项。这个对拍的习惯比任何debug技巧都管用我就是靠它从80分党变成一遍过的。最后分享一点个人感受。刚开始刷最短路专题时我也经历过背模板、套模板、WA到怀疑人生的阶段。后来发现把模板默写100遍不如真的搞清楚松弛和贪心正确性这两个概念——Dijkstra为什么不能在负权图上用、Floyd为什么k必须最外层这些原理想通了模板只是一个顺手的工具。如果你现在还在为某道题80分挠头我的建议是停下来把代码里的dist初始化、数组大小、建图方向这三样挨个检查一遍它们贡献了我个人踩坑记录里至少六成的问题。最短路这个专题练是练不完的但只要你把本文这套模板和排查思路吃透洛谷上大多数最短路题都会变成送分题。