第一次看到Floyd算法那段三层for循环时我愣了几秒——就这不到十行代码竟然能把整张图所有点对之间的最短路径全算完。后来我越看越觉得这玩意儿挺有意思它像极了一个热心肠的交通协管员拿着地图挨个路口问“从这儿到那儿走我这个路口是不是更近”问完第1个路口再问第2个一圈问下来任意两个路口之间的最佳走法都有了。今天咱就不整虚的直接把这个“交通协管员”的工作流程掰开揉碎连代码骨架一起看明白。如果你正在准备算法面试或者手头刚好有一个需要反复查询最短路径的小需求这篇文章应该能帮你在十分钟内彻底弄懂它顺带避开我当年踩过的几个坑。1. 为什么需要“挨个路口问”Floyd在最短路径家族中的定位1.1 最短路径问题的三种子类型单源、多源与全源最短路径问题听起来是一个问题实际按“起点有几个”能分成三类。单源最短路径是面试里最常见的给定一个起点s求s到其他所有点的最短距离Dijkstra、Bellman-Ford、SPFA都是干这个的。多源最短路径则是有一堆起点通常的做法是加一个超级源点把它和所有起点连上权值为0的边然后一次性跑单源算法本质还是单源。全源最短路径就不一样了它要求的是“任意两个点之间的最短距离”整张图所有点对都要算。你可以把它理解成打印一份整座城市的“任意两点距离表”而不是只回答“从家到公司怎么走”。最暴力的做法是拿单源算法跑n次也就是每个点都当一次起点。而Floyd算法是专门为这个问题设计的一次三重循环直接给出所有答案。1.2 真实场景里哪些问题其实是全源最短路径很多人觉得全源最短路径听起来很“教科书”平时用不上。其实不是的你身边到处都是。比如公交地铁换乘规划你想知道任意两个站之间最少换乘几次这就是一个全源问题——你不可能只为一个起点站服务用户可能从任何一站上车。再比如社交关系链有些人喜欢算“A和B之间隔着几层关系”本质是在一张好友关系图上求全源最短路径。还有物流调度我做过的一个内部小工具就是给几十个网点的包裹转运排线路因为每个网点都可能成为发货方所以干脆把所有网点两两之间的最短运输距离预先算好存起来之后任何一单查询都直接查表速度飞快。这些场景的共同特点是查询是随机的、高频的但图本身是相对静态的。这时候预计算一张全源距离表比每次查询都现场跑一遍单源算法划算得多。1.3 Floyd的卖点与代价极致简洁的代码和O(n³)的复杂度Floyd算法的卖点非常直白代码极短逻辑极其对称短到不容易写错。它不需要复杂的堆结构不需要维护访问标记不需要处理松弛顺序一个三重循环就是全部。代价也很直白时间复杂度O(n³)空间复杂度O(n²)。这意味着它不适合节点数特别多的图。以我个人的体感数据量在500个节点以内时Floyd是很好用的到了1000以上就要慎重掂量一下运行时间了。但反过来想正因为它的实现成本几乎为零在很多数据规模小、图又比较稠密的场景里它反而是工程上的最优解——你花十分钟写完跑一次后面所有查询都变成O(1)查表。2. 交通协管员的“每日放行规则”动态规划状态设计的来龙去脉2.1 状态定义的关键允许经过哪些路口Floyd算法的核心是一个动态规划而动态规划最关键的就是状态定义。这里的定义是这样的f[k][i][j] 表示“只允许经过编号为0到k的节点作为中间节点”时从i走到j的最短路径长度。注意“中间节点”三个字起点i和终点j不算在内。也就是说一开始k等于-1的时候路径上不能有任何中间节点只能i直接到j这就是初始邻接矩阵。随着k从0增加到n-1允许“借道”的节点越来越多距离自然越来越短或不变最终kn-1时就得到了全图所有点对的最短路径。这个定义是理解整个算法的钥匙。很多人直接把三维状态抛到脑后死记外层循环是中间节点虽然也能写出代码但一旦遇到变种题就抓瞎。我建议你花两分钟把f[k][i][j]这个定义在脑子里钉死后面所有东西都顺了。2.2 状态转移方程和“插队”逻辑有了状态定义转移方程就很自然了。考虑从i到j只允许经过前k个节点那么第k个节点也就是新放行的路口到底用不用两种可能不用它那么问题变成只允许经过前k-1个节点也就是 f[k-1][i][j]。用它那么路径拆成两段i先走到k再k走到j。注意这两段都只允许经过前k-1个节点因为k作为中转站只能出现一次不能在它的子路径里又绕回自己。所以转移方程就是f[k][i][j] min(f[k-1][i][j], f[k-1][i][k] f[k-1][k][j])这个方程用“交通协管员”的话说就是新路口k今天上岗我来问所有起点和终点对“你们原来的走法比我这儿中转一下还快吗如果更快就把路线改成从我这儿过。”为什么这样拆是完备的因为任何一条从i到j的路径要么真的经过了k要么完全没经过k没有第三种情况。我们只是把所有经过k的情况统一拆成“i到k段”加“k到j段”来比较而这两段各自又是在更小的节点集合内的最优解——这就是动态规划的最优子结构。2.3 为什么最优路径不会“绕路经过同一个中间点”这里有一个隐藏问题值得想清楚如果一条路径经过同一个节点两次比如i→a→b→a→j那它还算“最短路径”的候选吗答案是不需要。假设中间出现了从a绕一圈又回到a的环如果这个环的权值是正的那我删掉这段环整个路径更短所以原路径根本不可能是最短的如果环的权值是负的那更麻烦我可以在这个环里无限转圈每转一圈距离还变小所谓“最短”根本不存在这就是后面要说的负权环如果环权是0删掉它不影响结果。所以讨论最短路径时我们只需要关心每个中间节点最多出现一次的简单路径。Floyd逐轮放行中间节点每一轮相当于在候选集合里多加一个“可用节点”而最优路径上每个节点至多出现一次因此“逐轮加入节点”这个过程不会把真正的答案漏掉。3. 不到十行的核心代码代码骨架逐行拆解与滚动数组原理3.1 先看Python代码骨架代码骨架其实就一个三重循环。下面是我通常用的写法INF 10 ** 9 n len(dist) for k in range(n): # k是“交通协管员”今天放行的路口 for i in range(n): if dist[i][k] INF: continue # i到k都不通直接跳过 for j in range(n): nd dist[i][k] dist[k][j] if nd dist[i][j]: dist[i][j] ndC版本几乎没有差别const int INF 0x3f3f3f3f; for (int k 0; k n; k) for (int i 0; i n; i) for (int j 0; j n; j) if (dist[i][j] dist[i][k] dist[k][j]) dist[i][j] dist[i][k] dist[k][j];这里dist就是二维邻接矩阵初始时dist[i][i]0有边的填边权没边的填INF。跑完三重循环后dist[i][j]就是i到j的最短路径长度。就这么简单真的。3.2 为什么k必须是外层循环很多人刚开始写Floyd时会把循环顺序搞乱尤其会把k放在最内层。这里必须说清楚k必须是最外层。原因在于状态转移方程里f[k][i][j]依赖的是f[k-1][i][j]、f[k-1][i][k]、f[k-1][k][j]也就是说第k轮决策只能基于第k-1轮已经算完的结果不能在本轮计算过程中混入“未来”的信息。如果k放在最内层那么计算dist[i][j]时用到的dist[i][k]或dist[k][j]可能已经被当前这轮循环提前更新过了而且那次更新里可能已经借用了编号大于k的节点——相当于协管员还没“放行”某个路口呢路线里却已经偷偷绕过去了。这就会破环动态规划按阶段推进的语义得到的结果可能不是真正的全源最短路径。听起来有点抽象但我当年自己验证过把k放内层三个点的简单图都能算错。所以这个顺序不是代码风格问题是正确性问题k必须牢牢锁在最外层。3.3 滚动数组背后的数学依据细心的读者会发现代码里我们并没有真的开一个三维数组f[k][i][j]而是在二维dist上原地更新。这就带来一个问题第k轮更新dist[i][j]时会不会用到已经被“污染”的dist[i][k]或dist[k][j]答案是在没有负权环的正常图里不会。我们来看两个关键比较dist[i][k]在本轮可能被更新成dist[i][k] dist[k][k]而dist[k][k]初始值是0。如果它参与的比较dist[i][k] dist[k][k] dist[i][k]成立那就意味着dist[k][k] 0这恰恰说明存在负权环。所以正常图中dist[k][k]一直是0dist[i][k]这一轮不会被自己更新。同理dist[k][j]也不会在本轮变小。于是第k轮更新dist[i][j]时读到的dist[i][k]和dist[k][j]仍然是上一轮结束时的值和三维数组的语义完全一致。这就是Floyd能压缩成二维数组原地更新的根本原因也是它代码能这么短的前提。理解这一点比单纯背代码有用得多。3.4 小优化与语言差异Python版本的代码里我加了一个小剪枝if dist[i][k] INF: continue。如果i到k本来就不通那dist[i][k] dist[k][j]大概率还是INF根本没有比较的价值。这个优化在稀疏图上尤其明显能省掉大量无效加法。还有一个细节是语言差异。Python纯三层循环很慢同样是n500的稠密图C大概1秒内跑完Python可能要好几分钟。如果数据规模确实到了500以上我的建议是直接换C或者用Python的numpy做矩阵化改造但那个只适合纯距离计算场景一旦要同步更新路径矩阵就麻烦了。这个取舍后面第6章还会展开讲。4. 最容易翻车的三个边界问题INF选择、负权边与负权环4.1 INF的经典陷阱溢出与误判Floyd的代码里INF的选取是个大坑坑到每次面试都有人栽。在C里很多人顺手就用INT_MAX也就是0x7fffffff。问题来了dist[i][k]和dist[k][j]都是INT_MAX两个相加直接溢出变成负数。负数的值比任何正权值都小于是那些本来不可达的点对会被判定成“有一条权值为负数的超级短路径”整个距离表全毁了。正确的做法是用一个“略小于”真正无穷大的数比如经典的0x3f3f3f3f。这个数的十进制是1061109567两个相加是2122219134刚好小于INT_MAX的2147483647不会溢出成负数。而且它还有一个巨大的便利memset(dist, 0x3f, sizeof(dist))可以把整个数组按字节填成0x3f3f3f3f一行代码完成初始化这是竞赛圈把它当“通用无穷大”的根本原因。在Python里没有溢出问题但判断时要注意别用dist[i][j] INF。因为两个INF相加会得到2 * INF你存进数组的可能是一个大于INF的数。所以判断不可达要用dist[i][j] INF // 2这种写法。4.2 负权边的兼容性与条件Floyd算法允许图中存在负权边这比Dijkstra强不少。Dijkstra基于贪心一旦某个点的距离被确定就不再更新遇到后面突然出现一条负权边能刷新它时就抓瞎了。而Floyd每一轮都会把所有点对重新比较一遍不存在“锁定某个答案”的问题所以负权边对它来说只是普通的边权值。举个具体例子假设有三条边0→1权值50→2权值12→1权值-4。0到1的直接距离是5但正确的答案是-3因为可以先走0→2再走2→1总权值是1 (-4) -3。在Floyd里当k2那一轮dist[0][2] dist[2][1] 1 (-4) -3小于原来的5于是dist[0][1]被更新成-3。但必须强调一个前提图中不能有负权环。什么叫负权环就是从某个点出发绕一圈回到自己总权值还是负的。如果有这种环最短路径就没有意义了——你可以在环里无限绕圈每绕一圈距离还变小哪有什么“最短”。4.3 负权环检测Floyd也有一手Floyd跑完之后检测负权环的办法出乎意料地简单检查对角线。初始化时dist[i][i]0这是从i到i的最短距离的下界。如果图中存在负权环那么在Floyd的三重循环中会有一条从i出发回到i的路径总权值小于0于是dist[i][i]会被更新成一个负数。所以跑完Floyd后只要遍历一次对角线发现任何dist[i][i] 0就说明图中存在负权环。这个特性还可以玩出一些有趣的应用比如在外汇报率套利检测里把汇率取对数后建模成边权用Floyd检测是否存在乘积大于1的兑换环本质就是负环检测。当然这是后话至少说明对角线不是白留的。5. 从“知道多远”到“走哪条路”完整路径重构的实现细节5.1 只存距离不够需要一张“指路牌”Floyd的标准写法只更新了dist数组算出来的只是“任意两点之间的距离”。但很多实战场景里光知道距离没用你还得知道线路怎么走。这时候就需要额外维护一个路径矩阵。最推荐的做法是维护一个nxt矩阵nxt[i][j]表示从i出发到j的最短路径上i下一步应该走到哪个节点。你可以把它理解成十字路口放置的一张张指路牌写着“你要去某个地方第一脚先往哪走”。为什么记录“第一步”而不是“最后一步”因为路径还原时我们可以从起点出发根据指路牌一站一站走下去直到终点。这种正向链表的结构最符合直觉调试也方便。5.2 初始化与更新的配套写法nxt矩阵的初始化逻辑和dist一致nxt [[-1] * n for _ in range(n)] for i in range(n): for j in range(n): if i j: dist[i][j] 0 nxt[i][j] i elif 有边(i, j): # 根据你的邻接矩阵/边表替换 nxt[i][j] j # 能直接一步走到j在主循环里更新距离的同时必须同步更新nxt。这里有一个大家特别容易写错的地方for k in range(n): for i in range(n): if dist[i][k] INF: continue for j in range(n): nd dist[i][k] dist[k][j] if nd dist[i][j]: dist[i][j] nd nxt[i][j] nxt[i][k] # 关键不是k而是nxt[i][k]注意最后一行nxt[i][j]更新成nxt[i][k]而不是直接更新成k。为什么因为从i到k的最短路径上第一步走的不一定是k可能中间还要经过别的节点。比如i→a→k是i到k的最短路那i到j的最短路第一步自然也是走到a。直接写成k路径还原时就会跳过a导致路线缺失。这是我见过最多的实现错误没有之一。5.3 路径还原循环、递归两种写法有了nxt矩阵还原路径就很简单了。def get_path(start, end): if nxt[start][end] -1: return [] # 不可达 path [start] cur start while cur ! end: cur nxt[cur][end] if cur -1: return [] # 防止死循环 path.append(cur) return path这个循环是标准的“一路问指路牌”的过程。也可以写成递归的版本思路类似因为路径是i→某种方式→k→...→j你可以先找到中间那个k也就是nxt[i][j]对应的第一次跳转然后递归地还原i到k段和k到j段两边拼接。递归写法在思想上更贴近动态规划本身的拆解逻辑但实际工程里我更喜欢用循环因为递归深度最大到n虽然通常没问题但没必要冒这个风险。6. 工程实战里怎么选Floyd与多轮Dijkstra的取舍及实测表现6.1 稠密图优先什么时候Floyd才是首选是不是所有全源最短路径问题都该无脑用Floyd当然不是。判断标准就三句话看数据量、看图的稀疏程度、看是否有负权。图论里稀疏和稠密的分界一般看边数m和节点数n的关系。稠密图的边数接近n²稀疏图接近n。Floyd的复杂度是固定的O(n³)跟边数无关所以它天然适合稠密图——反正边都铺满了三重循环的操作量就是n³。而多轮Dijkstra就不一样了堆优化版Dijkstra跑n次复杂度是O(nm log n)。在稠密图里m接近n²这个复杂度比O(n³)还高。朴素版Dijkstra跑n次是O(n³)但常数比Floyd大不少因为每次找最小值和松弛的步骤都比Floyd的内层加法复杂。所以结论很清晰稠密图且n在500以内Floyd是无脑首选稀疏图且n很大多轮Dijkstra才是正解图里有负权边但无负环Floyd又能派上用场。下面这张表是我在实际项目里的选择逻辑。6.2 数据量与耗时我的实测参考我拿普通笔记本实际跑过几组数据给大家一个量级参考。下表是不同n下纯三重循环Floyd在Python和C里的大致耗时节点数n内层操作次数PythonC100100万零点几秒毫秒级5001.25亿5到15秒约1秒内100010亿不建议运行几秒到十几秒注意这只是量级参考实际耗时跟机器、编译器优化、是否提前剪枝都有关系。但趋势很明确Python的纯Python三层循环在n500以上就很吃力了这时候要不换语言要不剪枝优化跳过INF的i行要不干脆换算法。C能扛住n1000甚至更大但超过2000以后时间会明显拉开除非数据规模真的很小否则我不会把Floyd当默认选项。6.3 一张决策表收尾我把自己的选型逻辑整理成一张表方便你遇到具体问题时直接对号入座场景条件推荐方案核心理由全源、稠密图、n ≤ 500Floyd代码极短常数小实现成本最低全源、稀疏图、n很大多轮堆优化Dijkstra复杂度更优能扛大规模数据单源、边权非负Dijkstra标准解法效率最高单源、存在负权边Bellman-Ford或SPFA能正确处理负权且不必求全源需要检测负权环Floyd跑完后查对角线或Bellman-Ford两种思路看你对全源是否需要多次随机查询但图不变预计算全源距离表Floyd或n次Dijkstra查询时O(1)取数线上服务尤其合适最后一条很多人容易忽略。线上系统里如果图基本静态而查询是海量且随机的哪怕节点数上千我也会考虑离线预计算一张距离表运行时直接查表。这种“空间换时间”的思路其实比纠结Floyd和Dijkstra谁更快更重要。翻了这么多次车之后我现在看到一个最短路径问题第一反应不是背模板而是先问三个问题数据规模几号图是密是疏边权有负数吗三问之后Floyd是不是最优解基本就有答案了。至于那些“需要一个人扛住所有点对最短路径”的场合Floyd永远是最省心、最不容易写错的那个——虽然朴素得像个拿着地图的交通协管员但人家是真的把每一条路都问明白了。
