如果你已经能把Dijkstra堆优化、SPFA的SLF优化写到肌肉记忆那你大概率也被一个问题卡过题目要求求所有点对之间的最短距离怎么搞最稳更麻烦的是图里还有负权边又不能跑Dijkstra那怎么办我见过不少人的第一反应是“对每个起点跑一遍单源最短路”听着合理但对稠密图或者带负权的图来说这个方案很容易变得又慢又不正确。这个系列写到第11篇我想把Floyd算法真正讲透——不是丢一段模板代码让你背而是把它背后的状态设计、降维原理、路径回溯和边界坑全部拆开。哪怕你之前只是听说过这个名字看完也能自己推出来并且知道什么时候该用它、什么时候果断换别的算法。1. 全源最短路径到底是什么问题单源算法为什么顶不上1.1 单源与全源的本质差别单源最短路径指的是固定一个起点比如节点1求它到图中所有其他节点的最短距离。这类问题最常用的武器是Dijkstra、Bellman-Ford、SPFA。它们的共同点是一次计算只服务一个起点。全源最短路径则完全不同它要求任意两个节点之间的最短距离。这个问题至少有两种“笨办法”对每个节点都跑一次单源最短路加起来是n次。把图里所有路径枚举一遍显然不可行。第一种办法看起来简单但你得先选对单源算法。假设图里有负权边Dijkstra直接废掉因为你不能保证“当前选出的最近节点”以后不会被一条负权边更新。你只能退回到Bellman-Ford或者SPFA跑n次复杂度变成O(n * n * m)级别可以理解为三到四次层嵌套。如果图再稠密一点m接近n^2那总复杂度直接往O(n^4)方向走稍微大一点的图就彻底跑不动。所以全源最短路径不是单源最短路径的简单重复它是一个需要重新审视的问题。Floyd算法恰好用一个极短的O(n^3)三重循环一次性把所有点对的距离都算出来。1.2 Floyd算法在这种问题里的位置Floyd算法的思维出发点是“路径拼接”。设想i到j之间有一条最短路径这条路径上可能经过一堆中间节点。如果能逐步放宽“允许经过的中间节点集合”并不断修正任何两点之间的最短路那么最终收敛时所有点对距离就是全源最短路径。这也是Floyd算法最吸引人的地方所有操作都在一张邻接矩阵上进行。你不需要建邻接表不需要优先队列不需要处理复杂的出队入队。只需要一张二维表然后三层循环把表刷到稳定。此外Floyd对负权边天然免疫。只要图里没有负环Floyd就能给出正确结果这是Dijkstra做不到的。负权边在实际建模中并不少见比如某些目标函数是“收益费收益”的转换两个状态之间的转移代价可能是负值。我自己的使用经验里Floyd还有一个隐藏优势跑完之后任意两点之间的最短距离是O(1)查询。后续不管做动态规划、聚类、还是多组询问直接查表不需要再碰图结构。这比“现场临时跑一次Dijkstra”要好用很多尤其是查询次数非常多的时候。2. 三层循环背后的状态推导从三维DP到二维原地更新2.1 经典状态设计允许经过哪些中间节点很多人背Floyd的时候只知道三重循环长这样for k in 1..n for i in 1..n for j in 1..n dist[i][j] min(dist[i][j], dist[i][k] dist[k][j])但完全不知道这个k到底是什么。我从动态规划的角度给你拆开。定义一个三维状态dp[k][i][j] 表示从i到j只允许经过编号为1到k的节点作为中间节点时最短路径长度。注意dp[0][i][j]是什么中间节点一个都不允许经过那只能从i直接走到j。如果存在边就是边权不存在边就是正无穷。所以初始化时把邻接矩阵直接当作dp[0]。然后考虑dp[k][i][j]。当你把第k个节点加入“允许的中间节点集合”后从i到j的最短路径只可能分成两种完全不用第k个节点作为中间节点此时路径长度仍然是dp[k-1][i][j]。用第k个节点作为中间节点路径分为两段i先到k再从k到j长度是dp[k-1][i][k] dp[k-1][k][j]。所以状态转移方程是dp[k][i][j] min(dp[k-1][i][j], dp[k-1][i][k] dp[k-1][k][j])这个方程是整个Floyd算法的灵魂。所有的三重循环不过是在按k从小到大填这个三维表。2.2 为什么原地更新是安全的三维表二维化这是初学者最容易困惑的地方。按理说dp[k]的计算用到了dp[k-1]的值如果我用一个二维数组原地更新会不会把还没用上的旧值覆盖掉导致结果出错答案是不会但需要证明。核心关键是看dp[k][i][k]和dp[k][k][j]这两个值。先从定义出发dp[k][i][k]表示从i到k只允许经过前k个节点作为中间节点的最短距离。这里的端点也是k。如果这条路径中间又经过了k就会形成“走一圈回来”的效果比如i到某个节点再到k再回到k。最短路径里这种重复经过同一个中间节点的环一定可以去掉去掉后距离不会变大。所以真正的最短路径并不会把k当作自己的中间节点再用一次。因此dp[k][i][k]实际上等于dp[k-1][i][k]dp[k][k][j]实际上等于dp[k-1][k][j]现在再回到更新dist[i][j] min(dist[i][j], dist[i][k] dist[k][j])。表面上我们读的dist[i][k]和dist[k][j]可能是已经被第k轮更新过的值但刚才证明了它们更新后的值跟更新前完全一样所以用二维数组原地更新是严格等价的。这也是为什么Floyd的循环顺序必须是k在最外层i和j在内层随意。如果反过来把i或者j放最外层k放内层这个等价性就不成立结果会错得莫名其妙。2.3 一个更容易记住的直观解释如果你觉得上面的形式化推导太绕可以换一个生活化的比喻。把节点想象成一群联系人消息只能通过联系人之间互传。一开始每个人只知道和直接认识的人怎么联系。现在开始“开会”第1个人被拉进核心群全网更新的规则是任何人的消息如果经过1号中转会更短就改成这条新路线。然后是2号加入全网再更新一遍。每加入一个人消息中转的可能性就更丰富。Floyd里的k本质就是“当前核心群最后一个加入的人”。每加入一个人就要重新审视所有点和所有点之间的路径要不要通过这个新加入的家伙绕一下这个过程重复n次所有可能的中间节点组合都考虑完了距离自然收敛到全局最短路。这样想三重循环就不再是无脑嵌套而是一个清晰的“逐人加入、全网更新”过程。3. 手写一版能跑的Floyd初始化、三重循环、路径回溯3.1 邻接矩阵初始化重边、自环和无向图对称性写Floyd之前邻接矩阵的初始化直接决定你会不会在细节上翻车。自己到自己的距离初始化为0即dist[i][i] 0。没有边的位置初始化为一个很大的数一般叫INF。如果输入存在重边保留最小的那条。不能直接赋值要用min。如果是无向图加边时双向都要写有向图则只写方向。如果出现自环且权值为正dist[i][i]应该还是0因为最短路径没必要绕自己一圈。如果自环权值是负的dist[i][i]会被更新成负数这就是负环的信号后面专门说。路径矩阵的初始化和dist同步。我用path[i][j]表示从i到j这条路径上的“第一跳节点”初始时如果i可以直接到j第一跳就是j。这样将来还原路径时从i出发查第一跳再查第一跳的下一跳一直查到j为止。3.2 核心代码C和Python两种版本C版本可以直接存邻接矩阵缺点是最多容纳几百到几千个节点再大内存就吃紧。代码写法如下。#include bits/stdc.h using namespace std; const int MAXN 505; const int INF 0x3f3f3f3f; int dist[MAXN][MAXN]; int nxt[MAXN][MAXN]; // nxt[i][j] 表示从i出发到j的第一跳节点 void init(int n) { for (int i 1; i n; i) { for (int j 1; j n; j) { if (i j) dist[i][j] 0; else dist[i][j] INF; nxt[i][j] j; } } } void add_edge(int u, int v, int w) { dist[u][v] min(dist[u][v], w); // 重边取最小 } void floyd(int n) { for (int k 1; k n; k) { for (int i 1; i n; i) { if (dist[i][k] INF) continue; // 小优化跳掉不可能的路径 for (int j 1; j n; j) { if (dist[i][k] dist[k][j] dist[i][j]) { dist[i][j] dist[i][k] dist[k][j]; nxt[i][j] nxt[i][k]; } } } } } void print_path(int u, int v) { if (dist[u][v] INF) { cout no path endl; return; } int cur u; while (cur ! v) { cout cur - ; cur nxt[cur][v]; } cout v endl; }Python版本更简洁适合快速验证思路import sys def floyd(n, dist): nxt [[j if i ! j else None for j in range(n)] for i in range(n)] for k in range(n): for i in range(n): if dist[i][k] float(inf): continue for j in range(n): new_dist dist[i][k] dist[k][j] if new_dist dist[i][j]: dist[i][j] new_dist nxt[i][j] nxt[i][k] return dist, nxt注意C版里的INF用了0x3f3f3f3f这是一个经典取值约等于10.6亿。两个这样的INF相加大约是21.2亿还在int的表示范围内不会立即溢出成负数。这一点比直接用int的最大值要安全很多后面我还会细讲。3.3 用4节点的图手工推一遍矩阵变化光看代码还是不够直观我拿一个非常小的例子走一遍。图里有4个节点编号从1到4。边如下1到2权重32到3权重21到3权重83到4权重12到4权重7初始dist矩阵行是起点列是终点起点/终点12341038INF23027382014INF710一开始只有直达边。k1也就是允许节点1作为中间节点。走一遍i和j发现没有哪个路径能通过节点1获得明显优势。比如2到3原来直接是2如果绕13811反而更差。矩阵不变。k2允许节点2作为中间节点。这时1到3有两条路直达8或者1到2再到3代价325所以dist[1][3]更新为5。同样1到4原本不可达现在1到2再到43710所以dist[1][4]从INF变成10。3到1也对称更新为54到1更新为10。k3允许节点3作为中间节点。此时1到4的路可以走1到3再到4516比原来的10更短于是dist[1][4]更新为6。2到4也可以走2到3再到4213比原来的7更短dist[2][4]更新为3。同理4到1、4到2也分别被刷新。k4允许节点4作为中间节点。因为4只连了3几乎所有路径都没变短最终矩阵稳定。最终结果是起点/终点1234103562302335201463101到4的最短路径是1 - 2 - 3 - 4总距离6。这就是Floyd一步一步“松弛”出来的结果。3.4 路径还原维护next数组的三个关键点距离算完之后如果题目只是求长度那到此为止。但很多场景要求输出具体路径这时候next数组就必须维护好。第一个关键点初始化时nxt[i][j] j意思是默认从i直接跳到j。如果i和j之间根本没有边这个默认值也没关系因为dist是INF路径还原时会先判断不可达。第二个关键点更新dist[i][j]的时候必须同步更新nxt[i][j] nxt[i][k]。为什么是这个值因为新路径是i先走到“到k路径上的第一跳”然后再从k走到j。所以从i出发后第一步要走的节点就是nxt[i][k]。第三个关键点访问nxt[cur][v]的时候cur会不断变化但v始终保持终点不变。这样做是为了沿着第一跳链走到终点。如果dist是INF就不要进入这个循环否则可能死循环。很多人在更新距离时忘了维护路径矩阵等要输出路径才发现根本没法还原只能重新跑一遍BFS。别问我是怎么知道的。4. 负权边、负环与INFFloyd最容易被坑的三个细节4.1 能处理负权不能处理负环差在哪Dijkstra为什么一碰到负权边就失效因为它的贪心策略是“当前距离最近的节点一旦确定就不再更新”但负权边可能让一个节点在已经确定后又被一条新路径变得更短。Floyd没有这个贪心假设它枚举了所有可能的中间节点组合所以负权边对它来说只是普通的边权。但是负环是另一回事。如果图中存在一个环环上总权重为负那么沿着这个环反复转圈就能让路径代价无限减小。这种情况下最短路径没有意义不存在所谓的收敛结果。Floyd可以检测负环。原理很简单跑完正常的Floyd后如果存在某个i满足dist[i][i] 0说明从i出发绕一圈回来距离变成负的那就说明存在负环。为什么会这样正常情况下dist[i][i]初始是0任何正权环都会让dist[i][i]保持0或者变成更大的正数只有负环能让它变成负数。所以只要在Floyd结束之后扫描一遍对角线就能知道图里有没有负环。如果你想在计算过程中就发现负环可以加一个判断当dist[i][k] dist[k][j] dist[i][j]更新之后顺便检查dist[i][i]是否小于0。一旦发现直接停止计算因为后面所有结果都没有意义。4.2 无穷大的选取与溢出陷阱一开始学Floyd的人经常直接写INF 1e9或者干脆用int最大值。这两种都有隐患。先说int最大值2147483647。如果dist[i][k]和dist[k][j]都是这个值那dist[i][k] dist[k][j]会直接溢出成负数。一旦出现负数它必然小雨当前的dist[i][j]除非dist[i][j]也是负数结果就是因为你没判断INF错误地把一个“不可达”的路径更新成了负数。这个问题极其隐蔽跑小样例可能没事随机大图一来就全错。再说1e9。两个1e9相加等于2e9在int范围内但已经非常接近上限。虽然大部分时候不会溢出但如果你在不该加的时候加了判断不出来还是会污染矩阵。正规做法有两个在加法之前先判断dist[i][k]和dist[k][j]是否为INF是就跳过。把INF设为0x3f3f3f3f这样两个INF相加仍然是int范围内的正数不会溢出不致于污染然后靠“小于dist[i][j]”这个判断来过滤因为正常真实路径很难超过这个值。我自己的模板里会两种都做既判断又用0x3f3f3f3f。多写一行判断能省掉一晚上的排查时间。4.3 规模红线什么时候果断放弃FloydFloyd的复杂度O(n^3)这是它最大的天花板。给你一个粗略的体感估算当n 300时2700万次更新C轻松跑完Python也还算能接受。当n 500时1.25亿次更新C大概1秒上下Python会明显变慢。当n 1000时10亿次更新C也要好几秒甚至更多Python基本不可行。所以在竞赛或者面试题里看到n 300到500这个量级Floyd是正常选项看到n超过1000就要立刻转头想别的办法。内存也别忘了两张n*n矩阵各占4字节的话n1000时是8MBn3000时是72MBn5000时直接200MB很容易超出内存限制。很多初学者养成了“看到邻接矩阵就无脑Floyd”的习惯这是不对的。Floyd适合小规模全源最短路不适合大图。这一点必须时刻记住。5. 选型对比与变体扩展Floyd、Dijkstra、Bellman-Ford与Johnson怎么选5.1 四个算法的横向对比算法典型复杂度适用场景负权边负环检测备注FloydO(n^3)小规模全源最短路支持能实现极短查询O(1)n次Dijkstra堆优化O(n * m log n)稀疏图全源最短路不支持不能图中不能有负权单次Bellman-FordO(n * m)单源最短路、负环检测支持能全源需要跑n次JohnsonO(n * m log n)稀疏图全源最短路支持能通过重赋权消掉负权再跑n次Dijkstra这张表里最容易被忽略的是Johnson算法。它的思路是先跑一次Bellman-Ford给每个点算势能然后把所有边重赋权成非负值最后做n次Dijkstra。在稀疏图里Johnson通常比Floyd划算得多。5.2 我做选型的判断流程现在拿到一道最短路题目我不会急着写Floyd而是按下面这套顺序判断如果是单源问题直接进单源算法支线无负权用Dijkstra有负权用Bellman-Ford或SPFA要判负环就用Bellman-Ford。如果是全源问题先看n的大小。n小到500以内再问自己图里有没有负权有负权且稠密优先Floyd。有负权但很稀疏可以考虑Johnson。无负权且稀疏n次Dijkstra更稳。如果后续有大量“任意两点距离”的查询需求这时候就算n稍微大一点只要内存放得下我也会倾向用Floyd先预处理因为查询O(1)太省事了。举个例子状态压缩DP里经常要预先算好所有城市之间的最短路然后每步都查两个城市之间的代价。这种情况下Floyd的预计算结果就是整个DP的地基极其合适。5.3 传递闭包与bitset优化Floyd思想的变形Floyd的思想不只用于求最短路还能用于求有向图的传递闭包也就是判断任意两点之间是否存在可达路径。此时把边权换成布尔值“0/1”转移方程变成reach[i][j] reach[i][j] || (reach[i][k] reach[k][j])如果要追求极致优化可以使用bitset把一行压成一个整数。转移变成if (reach[i][k]) reach[i] | reach[k];这样一次可以处理一个整数位复杂度近似O(n^3 / 64)。n达到2000甚至3000都有机会跑过去。这种变形在求祖先关系、依赖关系、闭包判断的题目里非常好用。6. 实战感悟与测试方法从会背代码到真正用对6.1 看到什么题干特征第一反应该用Floyd刷题多了之后你会发现Floyd出场的信号非常明显题干明确说“任意两点之间的最短路径”。输入直接给了邻接矩阵。n在500以下甚至只有300以内。图里可能有负权边但保证无负环。后面还有大量询问需要快速查询点对距离。题目是图论与其他专题的组合比如状态压缩DP、最小生成树变体等。只要同时满足其中几项Floyd基本就是最佳选择。6.2 对拍测试与易错点核对表写算法最忌讳“我觉得没问题”。我自己的习惯是写一个暴力版本和Floyd对拍。具体做法是随机生成一个小图节点数10以内边随机加权重随机取正负。然后写一个全排列暴力或者每次BFS/枚举所有路径的版本跟Floyd的结果对比。跑上千组随机样例距离相等路径也还原正确才算这个实现真的靠谱。下面这张表是我每次写完Floyd都要过一遍的检查清单易错点典型症状解决办法INF设置过大或过小出现负数或错误更新用0x3f3f3f3f并在加算前判断INF重边只赋最后一条距离偏小或偏大加边用min自环处理错误正自环导致奇怪结果初始化dist[i][i]0无向图只加了单向边结果不对称加边时双向写入更新距离不更新next矩阵路径还原错误同步维护nxt[i][j]nxt[i][k]路径不可达时强行还原死循环先判断dist[u][v]是否为INF负环未检测距离不断变小无意义扫描dist[i][i] 0把这张表贴在代码模板旁边每次写完都对照一遍能省很多Debug时间。6.3 个人体会Floyd在工程里远比想象中好用很多人觉得Floyd只是竞赛里的小玩具实际工程项目里没人用。我自己的体会恰恰相反。有一次我做一个规模约300个节点的距离矩阵预处理任务节点之间有的有直接关系有的没有关系权重里还存在负数。如果每次查询都去临时跑Dijkstra响应时间根本没法看。但用Floyd把所有点对距离一次性算完后续任何查询都是查表代码量小结果稳定排查问题也方便。还有一次是在一个图论模型里需要判断两个节点之间能否通过中间节点串联当时直接用了传递闭包的bitset优化版本一次跑完所有可达性。Floyd思想的可迁移性真的被低估了。最后分享一个小技巧学Floyd的时候别急着背代码先自己在纸上写三维状态的转移方程然后想一想“为什么二维原地更新没事”。等你想明白了再去看代码你就能清楚地知道k、i、j三层的顺序为什么必须是那样。到这个程度Floyd才算真正长在你脑子里而不是停留在收藏夹里的一串字符。