当年面试字节的时候面试官问我“会Dijkstra吗”我说会然后他紧接着补了一句“那Floyd呢用一句话说清楚它的核心思想”。我当时愣了一下因为平时刷题基本都是Dijkstra的堆优化Floyd也就背过三重循环真要用一句话讲明白反而不太利索。后来自己把这块彻底啃了一遍才发现Floyd是个被严重低估的算法——它写起来最简单但背后的动态规划思想、循环顺序的讲究、路径回溯的细节每一个都值得好好盘一盘。这篇就来聊聊Floyd算法Floyd-Warshall算法它是什么、为什么能一次算出所有点对的最短路径、实际工程里有哪些坑以及什么时候该选它而不是Dijkstra。适合看这篇的人很明确准备算法面试的、做路径规划相关开发的、或者学过Floyd但一直停留在“背代码”阶段的同学。我争取把这套逻辑讲到“看完就能手写、写出来心里有底”的程度。1. 整体设计思路从邻接矩阵到全局最短路1.1 解决的问题本质Floyd算法解决的是多源最短路径问题给定一张有向图无向图也可以看成双向有向图求任意两个顶点之间的最短路径长度。换句话说跑完一遍Floyd之后你得到的是一个二维矩阵dist[i][j]表示从顶点i到顶点j的最短距离。这跟单源最短路有本质区别。Dijkstra跑一次只能得到一个起点到所有点的距离如果要求所有点对就得跑n次Dijkstra复杂度是O(n * m log n)。在稠密图m接近n²上这个开销会非常大而Floyd无论稠密稀疏时间复杂度都是稳定的O(n³)代码量却短得多。我当时在项目里第一次用到Floyd是一个交通换乘的demo。地图上一共就几十个站点但两两之间都要算最短通行时间。如果用Dijkstra跑几十次代码要处理堆、维护visited数组逻辑重复而且容易出bug。后来换成Floyd20行代码解决问题后面每次站点数据更新直接重新算一遍矩阵就行简单粗暴但非常可靠。1.2 Floyd最巧妙的视角把“经过哪些点”变成“能不能借道”Floyd的核心思想一句话概括逐步允许路径经过更多的中间顶点不断刷新任意两点之间的最短距离。听起来有点抽象我们拆开看。一开始dist[i][j]只允许直接走边i-j没有中间顶点接着允许经过顶点0作为中转然后允许经过顶点0和1再然后允许经过0、1、2……直到允许经过所有顶点。每多放行一个中间顶点就尝试用dist[i][k] dist[k][j]去更新dist[i][j]如果这条“绕路”比原来的直连路径更短就替换掉。这种“逐步放行中间点”的思路和动态规划里的子问题划分完全一致。你可以把它理解成我想知道从家到公司的最终最优路线那就先只允许你经过“小区门口”看看有没有更近的走法再允许你经过“地铁站”再看看最终所有建筑都允许经过了得到的一定是全局最优。注意这里的“中间顶点”是路径中可以经过的顶点集合不是指路径上某一个固定的点。每次外层循环k代表把编号为k的顶点加入到“可选中转集合”中。2. 核心细节解析状态转移与三重循环的玄机2.1 状态转移方程与滚动数组Floyd的动态规划定义其实有两个维度一个是起点i和终点j另一个是“当前允许经过的中间顶点集合”。用完整的状态表示就是dp[k][i][j]表示“从i到j只允许经过编号0到k作为中间顶点”的最短距离。转移方程是dp[k][i][j] min(dp[k-1][i][j], dp[k-1][i][k] dp[k-1][k][j])这里有两种情况要么经过第k个顶点那路径被拆成i-k和k-j两段要么不经过第k个顶点沿用之前的结果。但注意实际写代码时我们根本不开三维数组直接在一个二维dist上原地更新。为什么可以这样关键点在于dp[k-1][i][k]和dp[k-1][k][j]这两个值在更新dist[i][j]时不会被本轮已经更新的值污染。仔细看一眼当外层循环是k时内层i、j无论如何遍历dist[i][k]和dist[k][j]这些“跟k相关的距离”在它们被用于更新dist[i][j]之前其实不需要这一轮的k中转。因为dist[i][k]本身是“从i到k经过前k-1个中间点”的距离即使某一轮先更新了dist[i][k]那也是基于老的dist[i][k]加上dist[k][k]等于0得来的值不会变得更小所以不影响正确性。这就是为什么原地更新没问题也是Floyd能省掉一维空间的核心原因。2.2 为什么最外层循环必须是k这个坑值得多讲几句。很多人把三重循环写成for (int i 0; i n; i) for (int j 0; j n; j) for (int k 0; k n; k) if (dist[i][j] dist[i][k] dist[k][j]) dist[i][j] dist[i][k] dist[k][j];看起来好像也是同样的转移但结果是错的。为什么因为当i、j在外层时你遍历到某对(i,j)时dist[i][k]可能已经在本次“i循环”中通过其他k更新过了但这个更新可能依赖一个还没有被考虑完整的中转集合导致结果偏大或偏小。打个比方你要在“只能经过1号站”的情况下确定A到B的最短路就必须保证所有“经过1号站”的段比如A到1、1到B都已经处于“只能经过更小编号中间站”的稳定状态。如果k不是最外层你在计算A到B时A到1的最短距离可能还没算完因为它还需要经过编号更大的中间点拿一个不稳定值去更新结果自然不对。所以记住k在最外层是Floyd正确性的基石别的顺序运行快慢一样但结果是错的。这个点面试也经常拿来考察。2.3 初始化矩阵的含义与对角线的处理初始化最容易被忽略。正确做法是const int INF 1e9; for (int i 0; i n; i) for (int j 0; j n; j) dist[i][j] (i j ? 0 : (i到j有边 ? 边权 : INF));对角线dist[i][i]必须初始化为0这个不用多说自己到自己距离是0。关键是i ! j且没有直接边的情况必须赋值一个足够大的“无穷大”。关于INF的选择后面第四部分专门讲。这里还有一个常见误区如果图中有重边两条平行边初始化时取最小值如果输入是带负权边也照样初始化Floyd可以正确处理负权边只是不能有负权环。这一点比Dijkstra强不少。3. 实操过程手写一版能用的Floyd以及路径回溯3.1 C完整实现标准模板直接抄直接给一份我平时用的模板注释都写在关键位置#include bits/stdc.h using namespace std; const int MAXN 505; const int INF 0x3f3f3f3f; int dist[MAXN][MAXN]; int n, m; void floyd() { for (int k 0; k n; k) { for (int i 0; i n; i) { if (dist[i][k] INF) continue; // 小优化i到k不通就不用试 for (int j 0; j n; j) { if (dist[k][j] INF) continue; // k到j不通也不用试 if (dist[i][j] dist[i][k] dist[k][j]) { dist[i][j] dist[i][k] dist[k][j]; } } } } } int main() { cin n m; for (int i 0; i n; i) for (int j 0; j n; j) dist[i][j] (i j) ? 0 : INF; for (int i 0; i m; i) { int u, v, w; cin u v w; dist[u][v] min(dist[u][v], w); // 重边取最小 // 无向图再加一行: dist[v][u] min(dist[v][u], w); } floyd(); // 输出任意两点最短路 for (int i 0; i n; i) { for (int j 0; j n; j) { if (dist[i][j] INF) cout INF ; else cout dist[i][j] ; } cout \n; } return 0; }几个要点INF用0x3f3f3f3f是有讲究的下面细说提前判断dist[i][k]或dist[k][j]是不是INF能省掉大量无效加法实测在稀疏图上能快30%左右顶点编号从0开始写起来更自然如果输入是1到n循环前统一减一或者把循环范围改成1..n。3.2 路径回溯距离算出来了怎么打印完整路径很多教程只求最短距离但工程里往往需要完整路径。比如导航系统只告诉你“两地距离10公里”肯定不行你得给出走法。Floyd同样支持路径回溯做法是额外维护一个path[i][j]矩阵记录i到j的路径上j的前一个顶点是谁。更新策略很直接如果从i到j经过k更短那么i到j的路径就变成了“i到k的路径”接上“k到j的路径”所以path[i][j]应该更新为path[k][j]即j在“i到k再到j”这条路径上的前驱跟在k到j路径里的前驱一样。完整代码如下int path[MAXN][MAXN]; // path[i][j] 表示i到j最短路径上j的前驱顶点 void floyd_with_path() { // 初始化path for (int i 0; i n; i) for (int j 0; j n; j) path[i][j] (i j || dist[i][j] INF) ? -1 : i; for (int k 0; k n; k) { for (int i 0; i n; i) { if (dist[i][k] INF) continue; for (int j 0; j n; j) { if (dist[k][j] INF) continue; if (dist[i][j] dist[i][k] dist[k][j]) { dist[i][j] dist[i][k] dist[k][j]; path[i][j] path[k][j]; } } } } } void print_path(int u, int v) { if (path[u][v] -1) { cout No path\n; return; } vectorint route; route.push_back(v); while (v ! u) { v path[u][v]; route.push_back(v); } reverse(route.begin(), route.end()); for (int x : route) cout x ; cout \n; }注意初始化的细节如果i和j之间有直接边前驱初始化为i如果ij前驱设为-1或者i都行但要保证print_path里不会死循环。这里有个容易写错的地方更新path[i][j]时不能用path[i][k]而要用path[k][j]。因为拼接后的路径j的前驱应该是原来“k到j”路径上j的前驱不是“i到k”路径上j的前驱后者根本不是j这条线的上游。我当时第一次写就搞反了结果输出路径完全乱掉。3.3 Python实现简洁但要注意性能Python版本的Floyd代码可以非常短适合小型图、比赛快速验证、或者做算法演示import sys def floyd(n, dist): for k in range(n): for i in range(n): if dist[i][k] sys.maxsize: continue for j in range(n): if dist[k][j] sys.maxsize: continue nd dist[i][k] dist[k][j] if dist[i][j] nd: dist[i][j] nd return dist n 4 INF sys.maxsize dist [ [0, 3, INF, 7], [8, 0, 2, INF], [5, INF, 0, 1], [2, INF, INF, 0] ] res floyd(n, dist) for row in res: print(row)如果要处理几百个顶点的稠密图纯Python的三重循环会比较吃力。可以借助NumPy把内层的松弛操作向量化不过这种情况下通常要考虑是不是选Floyd本身就不合适。下一部分专门聊复杂度与选型。4. 复杂度分析与算法选型O(n³)到底能不能用4.1 时间与空间复杂度Floyd的时间复杂度是O(n³)空间复杂度是O(n²)。这个“n³”在很多场景下是致命伤也是面试官最爱追问的点。具体感受一下数量级n100三次方是100万轻轻松松n500是1.25亿现代CPU跑C大概一两秒n1000是10亿即使C也要在优化过的情况下十几秒起步n5000那是1250亿直接放弃。所以Floyd适合的是“顶点数量中等几百到一两千、但需要全源最短路径”的场景或者图本身很稠密、边数接近n²的场景。如果图很大但比较稀疏或者只需单源最短路Dijkstra系列才是正解。4.2 Floyd vs Dijkstra vs Bellman-Ford选型速查表我自己做选型时会用下面这张表快速判断算法时间复杂度空间单源/多源负权边负权环检测适用场景FloydO(n³)O(n²)多源支持可检测顶点少、全源、稠密图Dijkstra(堆优化)O(m log n)O(nm)单源不支持不可检测单源、非负权、稀疏图Bellman-FordO(nm)O(n)单源支持可检测单源、有负权边、边不多SPFA平均O(m)最坏O(nm)O(nm)单源支持可检测单源、有负权边、图稀疏这里有个陷阱Dijkstra在很多标准实现里没有考虑负权边一旦图里有负边结果直接错乱而Floyd天然支持负权边还能顺手检测负权环只要跑完发现dist[i][i] 0说明存在负环。这一点在涉及费用流、差价计算这些场景里特别有用。不过“支持负权边”不等于“无限支持”。如果图中存在一个负权环任何最短路算法都没有意义因为可以无限绕圈刷小距离Floyd检测到dist[i][i] 0之后应该立刻终止并报错。4.3 稠密图还是稀疏图实际选型经验我在实际开发里遇到过一个小型路网项目顶点是60个边快1500条接近完全图。当时第一版用Dijkstra跑了60次每次约O(m log n)一共大约60 * 1500 * 6 ≈ 54万次操作其实也不慢。但代码复杂度明显更高要写堆、写visited、循环60次重新初始化还要小心Dijkstra对负权边的误判。后来我重构时发现这个规模的Floyd也只要60³21.6万次操作不比60次Dijkstra慢反而代码短了不是一点半点。所以我的建议是顶点数几百以内、需要全源最短路时优先考虑Floyd。别被O(n³)吓住小规模图里它往往是最省心的答案。但顶点数超过1500或者更多时不要犹豫直接用Johnson算法或者多次Dijkstra。5. 经典应用Floyd不只是算最短距离5.1 传递闭包与Warshall算法Floyd的一个著名变体是Warshall算法用来求有向图的传递闭包——判断任意两点是否存在一条路径不关心路径长度。做法是把矩阵含义从“最短距离”改成“是否可达”转移逻辑从“加法比较”改成“或运算”for (int k 0; k n; k) for (int i 0; i n; i) for (int j 0; j n; j) reach[i][j] reach[i][j] || (reach[i][k] reach[k][j]);这个变体在关系数据库中很常见。比如某个权限系统里用户-角色-权限之间存在多级继承关系想知道“用户A最终能访问资源X吗”本质就是一个传递闭包问题用Warshall一次算完后续查询O(1)搞定。我当时接过的一个人力系统里组织架构的“领导汇报链”查询也是这么做的——求一个部门到另一个部门是否存在上下级传递路径。5.2 最少换乘问题无权图也能用Floyd不光适合带权图。遇到“最少换乘”“最少跳跃”这类无权图问题只需要把所有边权设为1然后跑一遍Floyd得到的dist就代表最少步数。某个内部工具里需要算两个知识库词条之间最短的跳转链词条A能否通过3次引用关系到达词条B就是直接把引用关系建成无权图然后跑Floyd的变体。不过这里要诚实说一句如果图特别大这种“无权最短路”用BFS从起点扫会更高效Floyd的优势只在“需要全源”的时候才体现。所以“最少换乘”如果只查一次BFS是王道如果系统里频繁要查询任意两点Floyd全算好再查是更好的选择。5.3 网络路由与价格最优组合在通信网络领域Floyd的思路也出现在路由协议里尤其是规模较小的域内路由、流量工程优化中。它的全源特性让每个节点都能维护一张到全网其他节点的最优转发表。现代大型网络里OSPF/IS-IS这类链路状态协议用的是Dijkstra的改进版——因为每个路由器只需要算自己到全网的最短路径不需要把所有点对最短路径都算出来。但如果某一天你需要在一张实验网络里做全网流量矩阵分析Floyd反而是最直观的工具算一次得到所有节点对之间最短路径直接生成OD矩阵。另一个有意思的场景是“最优组合价格”。假设你有多个中间商或物流渠道想把货物从A送到B中间可能经过若干个中转仓每个中转仓之间有不同的成本。把所有中转仓作为顶点、成本作为边权Floyd一次就能算出从任何出发仓到任何目的仓的最优成本路径。我在做供应链小demo的时候用过这个思路算是Floyd在业务层的一个典型映射。5.4 小型游戏地图的寻路替代方案游戏开发里A*是寻路主力但在规模不大的策略类游戏里Floyd也可以用来做预先计算好的全地图最短路径表。比如一张20x20的格子地图顶点400个边大概两三千条Floyd 400³6400万次操作在游戏启动时一次性算好也就一两秒。之后每帧查询任意两点之间最短路径和路径长度都是O(1)查表。缺点是一旦地图障碍物变化需要重新计算整张表——所以它更适合地图相对静态、需要大量寻路的场景比如回合制策略游戏里每个单位都要计算到目标的距离。从这个例子能看出来Floyd的本质是“用预处理时间换查询时间”适合查询频率远高于更新频率的场景。6. 常见问题与实战踩坑6.1 INF溢出与无穷大的选择这是Floyd最常见的坑INF选得不够大真实最短路居然比INF还大结果被错误地当成“不通”或者INF加上边权后溢出变成负数导致路径越更新越短。我建议C环境直接用0x3f3f3f3f它约等于10亿比int最大值小一些做加法时只要边权不超过几百万就不会溢出。而INT_MAX虽然更大但执行dist[i][k] dist[k][j]时如果两个INF相加直接溢出成负数整个矩阵全乱。Python则用float(inf)或sys.maxsize但float(inf)做加法不会溢出类型更干净。再强调一遍初始化顺序对角线初始化为0有直接边的初始化为边权多条边取最小没有直接边的初始化为INF不要一开始就把所有位置设成INF再慢慢加边那样会把自环变成INF。6.2 路径回溯的死循环问题前面提到过用path[i][j] path[k][j]更新时最怕的就是初始化或者更新出现环。比如ij时如果path初始化为-1然后while (v ! u)循环里如果u、v本来就不连通path[u][v]是-1取前驱时访问下标-1直接崩溃。所以打印路径前一定要判断path[u][v] -1。另外更新路径时如果忘了把path[i][j]同步更新会出现“距离是新的、路径是旧的”这种诡异状态排查起来特别费劲。我自己的习惯是把dist和path的更新写在同一行判断里尽量避免分开写造成不一致。6.3 无向图与有向图的初始化差异无向图本质上就是两条有向边初始化时记得同时更新dist[u][v]和dist[v][u]。容易漏掉的是“重边判断”也要双向做如果先读入u到v的权值再读入另一条u到v的权值只更新一个方向会出现不对称的最短路矩阵。我在一次练手时就踩过这个坑无向图数据里有一条边重复输入我没做min判断后一条直接把前一条覆盖了导致某些路径失效排查了半天才发现是初始化问题。后来形成肌肉记忆所有图的初始化代码一律写dist[u][v] min(dist[u][v], w)有向图再多写一行就完事。6.4 负权环的判断Floyd跑完之后只要出现dist[i][i] 0说明存在从i出发再回到i还能让距离变小的环也就是负权环。此时最短路没有定义应该中止继续使用结果。需要注意对ij的处理初始化时dist[i][i]0如果后续被更新成负数就是环检测的信号。但也有些情况下多源图里没有经过i本身的负环dist[i][i]仍然是0不代表没有负环——负环可能从i出发但路径上不回到i作为中间顶点。更严谨的判断是如果存在某个i使得dist[i][i] 0则图中存在负环如果所有dist[i][i] 0则无负环。但要小心Floyd过程中INF加上负边的组合可能在自环上出现“伪负值”所以INF的选择仍然很关键。6.5 小规模图也要注意剪枝虽然Floyd的三重循环已经非常简单但在n800~1000的边缘场景可以加两个剪枝如果dist[i][k]是INF直接跳过整个j循环如果dist[k][j]是INF跳过当前j。这两个判断几乎不消耗额外时间却能在稀疏图上把无效操作减少一大半。另外内层循环如果把j放中间、k放最内层虽然逻辑不对但很多编译器优化反而更激进性能好一点——前提是你得保证正确性。我的建议是平时先用标准k/i/j顺序保证逻辑清楚性能瓶颈真的出现时再用工具profiler验证是否值得为了性能改变循环顺序。6.6 问题速查表整理一个我在实际使用中经常参考的速查表现象可能原因解决办法dist对角线变成负数存在负权环检测并终止dist全变成很大的负数INF选择过大导致溢出改用0x3f3f3f3f或float(inf)输出路径乱序或死循环path更新错误或初始化问题检查path[i][j] path[k][j]打印前判-1i到j有路但输出INF初始化没考虑重边或漏加边初始化加min判断无向图距离不对称忘了同时更新对称位置初始化时双向更新换了循环顺序结果不对k不在最外层把k放最外层我真的建议读者第一次手写Floyd时故意把k放到最里面跑一遍观察结果错得有多离谱。这种“主动犯错”能帮你更深刻地理解循环顺序的意义比看十遍理论都管用。7. 我的几点实操心得最后分享几个我自己的体会希望能给你省点弯路。第一Floyd虽然代码短但绝不是“背下来就行”的算法。真正理解它在干嘛、为什么k要在外层、为什么可以原地更新这三点想通了之后哪怕多年不写也能在需要时5分钟重新推出来。我面试别人时也会专门问“如果让你从零推导Floyd你会怎么设计状态”能答上来的候选人算法基础基本都扎实。第二实际工程项目里Floyd的定位往往是“小规模全源查询的终极方案”。如果你发现一个功能需要频繁计算不同点对之间的最短路径图又不大别犹豫直接把Floyd写完放在初始化阶段跑一遍。相比缓存一堆单源结果Floyd的代码和维护成本低太多。第三路径回溯的path矩阵非常容易被忽略但真实业务几乎不会只给一个距离数字。我建议不管题目有没有要求都在学习阶段把path加上去练习一次就能记住更新规则。第四遇到大规模图时Floyd不合适但它的思想仍然值得借鉴。很多优化算法把“逐步扩充中间点集合”的思路拆解成半分治、分块处理或者在GPU上并行化Floyd。理解了基础版本往后看这些优化方案才不会一头雾水。这个算法我在好几个场景里重新捡起来用过每次都有种“还是老伙计靠谱”的感觉。希望你也能把它变成自己的熟练工具而不是躺在笔记本里吃灰。
Floyd算法核心解析：动态规划实现全源最短路径
当年面试字节的时候面试官问我“会Dijkstra吗”我说会然后他紧接着补了一句“那Floyd呢用一句话说清楚它的核心思想”。我当时愣了一下因为平时刷题基本都是Dijkstra的堆优化Floyd也就背过三重循环真要用一句话讲明白反而不太利索。后来自己把这块彻底啃了一遍才发现Floyd是个被严重低估的算法——它写起来最简单但背后的动态规划思想、循环顺序的讲究、路径回溯的细节每一个都值得好好盘一盘。这篇就来聊聊Floyd算法Floyd-Warshall算法它是什么、为什么能一次算出所有点对的最短路径、实际工程里有哪些坑以及什么时候该选它而不是Dijkstra。适合看这篇的人很明确准备算法面试的、做路径规划相关开发的、或者学过Floyd但一直停留在“背代码”阶段的同学。我争取把这套逻辑讲到“看完就能手写、写出来心里有底”的程度。1. 整体设计思路从邻接矩阵到全局最短路1.1 解决的问题本质Floyd算法解决的是多源最短路径问题给定一张有向图无向图也可以看成双向有向图求任意两个顶点之间的最短路径长度。换句话说跑完一遍Floyd之后你得到的是一个二维矩阵dist[i][j]表示从顶点i到顶点j的最短距离。这跟单源最短路有本质区别。Dijkstra跑一次只能得到一个起点到所有点的距离如果要求所有点对就得跑n次Dijkstra复杂度是O(n * m log n)。在稠密图m接近n²上这个开销会非常大而Floyd无论稠密稀疏时间复杂度都是稳定的O(n³)代码量却短得多。我当时在项目里第一次用到Floyd是一个交通换乘的demo。地图上一共就几十个站点但两两之间都要算最短通行时间。如果用Dijkstra跑几十次代码要处理堆、维护visited数组逻辑重复而且容易出bug。后来换成Floyd20行代码解决问题后面每次站点数据更新直接重新算一遍矩阵就行简单粗暴但非常可靠。1.2 Floyd最巧妙的视角把“经过哪些点”变成“能不能借道”Floyd的核心思想一句话概括逐步允许路径经过更多的中间顶点不断刷新任意两点之间的最短距离。听起来有点抽象我们拆开看。一开始dist[i][j]只允许直接走边i-j没有中间顶点接着允许经过顶点0作为中转然后允许经过顶点0和1再然后允许经过0、1、2……直到允许经过所有顶点。每多放行一个中间顶点就尝试用dist[i][k] dist[k][j]去更新dist[i][j]如果这条“绕路”比原来的直连路径更短就替换掉。这种“逐步放行中间点”的思路和动态规划里的子问题划分完全一致。你可以把它理解成我想知道从家到公司的最终最优路线那就先只允许你经过“小区门口”看看有没有更近的走法再允许你经过“地铁站”再看看最终所有建筑都允许经过了得到的一定是全局最优。注意这里的“中间顶点”是路径中可以经过的顶点集合不是指路径上某一个固定的点。每次外层循环k代表把编号为k的顶点加入到“可选中转集合”中。2. 核心细节解析状态转移与三重循环的玄机2.1 状态转移方程与滚动数组Floyd的动态规划定义其实有两个维度一个是起点i和终点j另一个是“当前允许经过的中间顶点集合”。用完整的状态表示就是dp[k][i][j]表示“从i到j只允许经过编号0到k作为中间顶点”的最短距离。转移方程是dp[k][i][j] min(dp[k-1][i][j], dp[k-1][i][k] dp[k-1][k][j])这里有两种情况要么经过第k个顶点那路径被拆成i-k和k-j两段要么不经过第k个顶点沿用之前的结果。但注意实际写代码时我们根本不开三维数组直接在一个二维dist上原地更新。为什么可以这样关键点在于dp[k-1][i][k]和dp[k-1][k][j]这两个值在更新dist[i][j]时不会被本轮已经更新的值污染。仔细看一眼当外层循环是k时内层i、j无论如何遍历dist[i][k]和dist[k][j]这些“跟k相关的距离”在它们被用于更新dist[i][j]之前其实不需要这一轮的k中转。因为dist[i][k]本身是“从i到k经过前k-1个中间点”的距离即使某一轮先更新了dist[i][k]那也是基于老的dist[i][k]加上dist[k][k]等于0得来的值不会变得更小所以不影响正确性。这就是为什么原地更新没问题也是Floyd能省掉一维空间的核心原因。2.2 为什么最外层循环必须是k这个坑值得多讲几句。很多人把三重循环写成for (int i 0; i n; i) for (int j 0; j n; j) for (int k 0; k n; k) if (dist[i][j] dist[i][k] dist[k][j]) dist[i][j] dist[i][k] dist[k][j];看起来好像也是同样的转移但结果是错的。为什么因为当i、j在外层时你遍历到某对(i,j)时dist[i][k]可能已经在本次“i循环”中通过其他k更新过了但这个更新可能依赖一个还没有被考虑完整的中转集合导致结果偏大或偏小。打个比方你要在“只能经过1号站”的情况下确定A到B的最短路就必须保证所有“经过1号站”的段比如A到1、1到B都已经处于“只能经过更小编号中间站”的稳定状态。如果k不是最外层你在计算A到B时A到1的最短距离可能还没算完因为它还需要经过编号更大的中间点拿一个不稳定值去更新结果自然不对。所以记住k在最外层是Floyd正确性的基石别的顺序运行快慢一样但结果是错的。这个点面试也经常拿来考察。2.3 初始化矩阵的含义与对角线的处理初始化最容易被忽略。正确做法是const int INF 1e9; for (int i 0; i n; i) for (int j 0; j n; j) dist[i][j] (i j ? 0 : (i到j有边 ? 边权 : INF));对角线dist[i][i]必须初始化为0这个不用多说自己到自己距离是0。关键是i ! j且没有直接边的情况必须赋值一个足够大的“无穷大”。关于INF的选择后面第四部分专门讲。这里还有一个常见误区如果图中有重边两条平行边初始化时取最小值如果输入是带负权边也照样初始化Floyd可以正确处理负权边只是不能有负权环。这一点比Dijkstra强不少。3. 实操过程手写一版能用的Floyd以及路径回溯3.1 C完整实现标准模板直接抄直接给一份我平时用的模板注释都写在关键位置#include bits/stdc.h using namespace std; const int MAXN 505; const int INF 0x3f3f3f3f; int dist[MAXN][MAXN]; int n, m; void floyd() { for (int k 0; k n; k) { for (int i 0; i n; i) { if (dist[i][k] INF) continue; // 小优化i到k不通就不用试 for (int j 0; j n; j) { if (dist[k][j] INF) continue; // k到j不通也不用试 if (dist[i][j] dist[i][k] dist[k][j]) { dist[i][j] dist[i][k] dist[k][j]; } } } } } int main() { cin n m; for (int i 0; i n; i) for (int j 0; j n; j) dist[i][j] (i j) ? 0 : INF; for (int i 0; i m; i) { int u, v, w; cin u v w; dist[u][v] min(dist[u][v], w); // 重边取最小 // 无向图再加一行: dist[v][u] min(dist[v][u], w); } floyd(); // 输出任意两点最短路 for (int i 0; i n; i) { for (int j 0; j n; j) { if (dist[i][j] INF) cout INF ; else cout dist[i][j] ; } cout \n; } return 0; }几个要点INF用0x3f3f3f3f是有讲究的下面细说提前判断dist[i][k]或dist[k][j]是不是INF能省掉大量无效加法实测在稀疏图上能快30%左右顶点编号从0开始写起来更自然如果输入是1到n循环前统一减一或者把循环范围改成1..n。3.2 路径回溯距离算出来了怎么打印完整路径很多教程只求最短距离但工程里往往需要完整路径。比如导航系统只告诉你“两地距离10公里”肯定不行你得给出走法。Floyd同样支持路径回溯做法是额外维护一个path[i][j]矩阵记录i到j的路径上j的前一个顶点是谁。更新策略很直接如果从i到j经过k更短那么i到j的路径就变成了“i到k的路径”接上“k到j的路径”所以path[i][j]应该更新为path[k][j]即j在“i到k再到j”这条路径上的前驱跟在k到j路径里的前驱一样。完整代码如下int path[MAXN][MAXN]; // path[i][j] 表示i到j最短路径上j的前驱顶点 void floyd_with_path() { // 初始化path for (int i 0; i n; i) for (int j 0; j n; j) path[i][j] (i j || dist[i][j] INF) ? -1 : i; for (int k 0; k n; k) { for (int i 0; i n; i) { if (dist[i][k] INF) continue; for (int j 0; j n; j) { if (dist[k][j] INF) continue; if (dist[i][j] dist[i][k] dist[k][j]) { dist[i][j] dist[i][k] dist[k][j]; path[i][j] path[k][j]; } } } } } void print_path(int u, int v) { if (path[u][v] -1) { cout No path\n; return; } vectorint route; route.push_back(v); while (v ! u) { v path[u][v]; route.push_back(v); } reverse(route.begin(), route.end()); for (int x : route) cout x ; cout \n; }注意初始化的细节如果i和j之间有直接边前驱初始化为i如果ij前驱设为-1或者i都行但要保证print_path里不会死循环。这里有个容易写错的地方更新path[i][j]时不能用path[i][k]而要用path[k][j]。因为拼接后的路径j的前驱应该是原来“k到j”路径上j的前驱不是“i到k”路径上j的前驱后者根本不是j这条线的上游。我当时第一次写就搞反了结果输出路径完全乱掉。3.3 Python实现简洁但要注意性能Python版本的Floyd代码可以非常短适合小型图、比赛快速验证、或者做算法演示import sys def floyd(n, dist): for k in range(n): for i in range(n): if dist[i][k] sys.maxsize: continue for j in range(n): if dist[k][j] sys.maxsize: continue nd dist[i][k] dist[k][j] if dist[i][j] nd: dist[i][j] nd return dist n 4 INF sys.maxsize dist [ [0, 3, INF, 7], [8, 0, 2, INF], [5, INF, 0, 1], [2, INF, INF, 0] ] res floyd(n, dist) for row in res: print(row)如果要处理几百个顶点的稠密图纯Python的三重循环会比较吃力。可以借助NumPy把内层的松弛操作向量化不过这种情况下通常要考虑是不是选Floyd本身就不合适。下一部分专门聊复杂度与选型。4. 复杂度分析与算法选型O(n³)到底能不能用4.1 时间与空间复杂度Floyd的时间复杂度是O(n³)空间复杂度是O(n²)。这个“n³”在很多场景下是致命伤也是面试官最爱追问的点。具体感受一下数量级n100三次方是100万轻轻松松n500是1.25亿现代CPU跑C大概一两秒n1000是10亿即使C也要在优化过的情况下十几秒起步n5000那是1250亿直接放弃。所以Floyd适合的是“顶点数量中等几百到一两千、但需要全源最短路径”的场景或者图本身很稠密、边数接近n²的场景。如果图很大但比较稀疏或者只需单源最短路Dijkstra系列才是正解。4.2 Floyd vs Dijkstra vs Bellman-Ford选型速查表我自己做选型时会用下面这张表快速判断算法时间复杂度空间单源/多源负权边负权环检测适用场景FloydO(n³)O(n²)多源支持可检测顶点少、全源、稠密图Dijkstra(堆优化)O(m log n)O(nm)单源不支持不可检测单源、非负权、稀疏图Bellman-FordO(nm)O(n)单源支持可检测单源、有负权边、边不多SPFA平均O(m)最坏O(nm)O(nm)单源支持可检测单源、有负权边、图稀疏这里有个陷阱Dijkstra在很多标准实现里没有考虑负权边一旦图里有负边结果直接错乱而Floyd天然支持负权边还能顺手检测负权环只要跑完发现dist[i][i] 0说明存在负环。这一点在涉及费用流、差价计算这些场景里特别有用。不过“支持负权边”不等于“无限支持”。如果图中存在一个负权环任何最短路算法都没有意义因为可以无限绕圈刷小距离Floyd检测到dist[i][i] 0之后应该立刻终止并报错。4.3 稠密图还是稀疏图实际选型经验我在实际开发里遇到过一个小型路网项目顶点是60个边快1500条接近完全图。当时第一版用Dijkstra跑了60次每次约O(m log n)一共大约60 * 1500 * 6 ≈ 54万次操作其实也不慢。但代码复杂度明显更高要写堆、写visited、循环60次重新初始化还要小心Dijkstra对负权边的误判。后来我重构时发现这个规模的Floyd也只要60³21.6万次操作不比60次Dijkstra慢反而代码短了不是一点半点。所以我的建议是顶点数几百以内、需要全源最短路时优先考虑Floyd。别被O(n³)吓住小规模图里它往往是最省心的答案。但顶点数超过1500或者更多时不要犹豫直接用Johnson算法或者多次Dijkstra。5. 经典应用Floyd不只是算最短距离5.1 传递闭包与Warshall算法Floyd的一个著名变体是Warshall算法用来求有向图的传递闭包——判断任意两点是否存在一条路径不关心路径长度。做法是把矩阵含义从“最短距离”改成“是否可达”转移逻辑从“加法比较”改成“或运算”for (int k 0; k n; k) for (int i 0; i n; i) for (int j 0; j n; j) reach[i][j] reach[i][j] || (reach[i][k] reach[k][j]);这个变体在关系数据库中很常见。比如某个权限系统里用户-角色-权限之间存在多级继承关系想知道“用户A最终能访问资源X吗”本质就是一个传递闭包问题用Warshall一次算完后续查询O(1)搞定。我当时接过的一个人力系统里组织架构的“领导汇报链”查询也是这么做的——求一个部门到另一个部门是否存在上下级传递路径。5.2 最少换乘问题无权图也能用Floyd不光适合带权图。遇到“最少换乘”“最少跳跃”这类无权图问题只需要把所有边权设为1然后跑一遍Floyd得到的dist就代表最少步数。某个内部工具里需要算两个知识库词条之间最短的跳转链词条A能否通过3次引用关系到达词条B就是直接把引用关系建成无权图然后跑Floyd的变体。不过这里要诚实说一句如果图特别大这种“无权最短路”用BFS从起点扫会更高效Floyd的优势只在“需要全源”的时候才体现。所以“最少换乘”如果只查一次BFS是王道如果系统里频繁要查询任意两点Floyd全算好再查是更好的选择。5.3 网络路由与价格最优组合在通信网络领域Floyd的思路也出现在路由协议里尤其是规模较小的域内路由、流量工程优化中。它的全源特性让每个节点都能维护一张到全网其他节点的最优转发表。现代大型网络里OSPF/IS-IS这类链路状态协议用的是Dijkstra的改进版——因为每个路由器只需要算自己到全网的最短路径不需要把所有点对最短路径都算出来。但如果某一天你需要在一张实验网络里做全网流量矩阵分析Floyd反而是最直观的工具算一次得到所有节点对之间最短路径直接生成OD矩阵。另一个有意思的场景是“最优组合价格”。假设你有多个中间商或物流渠道想把货物从A送到B中间可能经过若干个中转仓每个中转仓之间有不同的成本。把所有中转仓作为顶点、成本作为边权Floyd一次就能算出从任何出发仓到任何目的仓的最优成本路径。我在做供应链小demo的时候用过这个思路算是Floyd在业务层的一个典型映射。5.4 小型游戏地图的寻路替代方案游戏开发里A*是寻路主力但在规模不大的策略类游戏里Floyd也可以用来做预先计算好的全地图最短路径表。比如一张20x20的格子地图顶点400个边大概两三千条Floyd 400³6400万次操作在游戏启动时一次性算好也就一两秒。之后每帧查询任意两点之间最短路径和路径长度都是O(1)查表。缺点是一旦地图障碍物变化需要重新计算整张表——所以它更适合地图相对静态、需要大量寻路的场景比如回合制策略游戏里每个单位都要计算到目标的距离。从这个例子能看出来Floyd的本质是“用预处理时间换查询时间”适合查询频率远高于更新频率的场景。6. 常见问题与实战踩坑6.1 INF溢出与无穷大的选择这是Floyd最常见的坑INF选得不够大真实最短路居然比INF还大结果被错误地当成“不通”或者INF加上边权后溢出变成负数导致路径越更新越短。我建议C环境直接用0x3f3f3f3f它约等于10亿比int最大值小一些做加法时只要边权不超过几百万就不会溢出。而INT_MAX虽然更大但执行dist[i][k] dist[k][j]时如果两个INF相加直接溢出成负数整个矩阵全乱。Python则用float(inf)或sys.maxsize但float(inf)做加法不会溢出类型更干净。再强调一遍初始化顺序对角线初始化为0有直接边的初始化为边权多条边取最小没有直接边的初始化为INF不要一开始就把所有位置设成INF再慢慢加边那样会把自环变成INF。6.2 路径回溯的死循环问题前面提到过用path[i][j] path[k][j]更新时最怕的就是初始化或者更新出现环。比如ij时如果path初始化为-1然后while (v ! u)循环里如果u、v本来就不连通path[u][v]是-1取前驱时访问下标-1直接崩溃。所以打印路径前一定要判断path[u][v] -1。另外更新路径时如果忘了把path[i][j]同步更新会出现“距离是新的、路径是旧的”这种诡异状态排查起来特别费劲。我自己的习惯是把dist和path的更新写在同一行判断里尽量避免分开写造成不一致。6.3 无向图与有向图的初始化差异无向图本质上就是两条有向边初始化时记得同时更新dist[u][v]和dist[v][u]。容易漏掉的是“重边判断”也要双向做如果先读入u到v的权值再读入另一条u到v的权值只更新一个方向会出现不对称的最短路矩阵。我在一次练手时就踩过这个坑无向图数据里有一条边重复输入我没做min判断后一条直接把前一条覆盖了导致某些路径失效排查了半天才发现是初始化问题。后来形成肌肉记忆所有图的初始化代码一律写dist[u][v] min(dist[u][v], w)有向图再多写一行就完事。6.4 负权环的判断Floyd跑完之后只要出现dist[i][i] 0说明存在从i出发再回到i还能让距离变小的环也就是负权环。此时最短路没有定义应该中止继续使用结果。需要注意对ij的处理初始化时dist[i][i]0如果后续被更新成负数就是环检测的信号。但也有些情况下多源图里没有经过i本身的负环dist[i][i]仍然是0不代表没有负环——负环可能从i出发但路径上不回到i作为中间顶点。更严谨的判断是如果存在某个i使得dist[i][i] 0则图中存在负环如果所有dist[i][i] 0则无负环。但要小心Floyd过程中INF加上负边的组合可能在自环上出现“伪负值”所以INF的选择仍然很关键。6.5 小规模图也要注意剪枝虽然Floyd的三重循环已经非常简单但在n800~1000的边缘场景可以加两个剪枝如果dist[i][k]是INF直接跳过整个j循环如果dist[k][j]是INF跳过当前j。这两个判断几乎不消耗额外时间却能在稀疏图上把无效操作减少一大半。另外内层循环如果把j放中间、k放最内层虽然逻辑不对但很多编译器优化反而更激进性能好一点——前提是你得保证正确性。我的建议是平时先用标准k/i/j顺序保证逻辑清楚性能瓶颈真的出现时再用工具profiler验证是否值得为了性能改变循环顺序。6.6 问题速查表整理一个我在实际使用中经常参考的速查表现象可能原因解决办法dist对角线变成负数存在负权环检测并终止dist全变成很大的负数INF选择过大导致溢出改用0x3f3f3f3f或float(inf)输出路径乱序或死循环path更新错误或初始化问题检查path[i][j] path[k][j]打印前判-1i到j有路但输出INF初始化没考虑重边或漏加边初始化加min判断无向图距离不对称忘了同时更新对称位置初始化时双向更新换了循环顺序结果不对k不在最外层把k放最外层我真的建议读者第一次手写Floyd时故意把k放到最里面跑一遍观察结果错得有多离谱。这种“主动犯错”能帮你更深刻地理解循环顺序的意义比看十遍理论都管用。7. 我的几点实操心得最后分享几个我自己的体会希望能给你省点弯路。第一Floyd虽然代码短但绝不是“背下来就行”的算法。真正理解它在干嘛、为什么k要在外层、为什么可以原地更新这三点想通了之后哪怕多年不写也能在需要时5分钟重新推出来。我面试别人时也会专门问“如果让你从零推导Floyd你会怎么设计状态”能答上来的候选人算法基础基本都扎实。第二实际工程项目里Floyd的定位往往是“小规模全源查询的终极方案”。如果你发现一个功能需要频繁计算不同点对之间的最短路径图又不大别犹豫直接把Floyd写完放在初始化阶段跑一遍。相比缓存一堆单源结果Floyd的代码和维护成本低太多。第三路径回溯的path矩阵非常容易被忽略但真实业务几乎不会只给一个距离数字。我建议不管题目有没有要求都在学习阶段把path加上去练习一次就能记住更新规则。第四遇到大规模图时Floyd不合适但它的思想仍然值得借鉴。很多优化算法把“逐步扩充中间点集合”的思路拆解成半分治、分块处理或者在GPU上并行化Floyd。理解了基础版本往后看这些优化方案才不会一头雾水。这个算法我在好几个场景里重新捡起来用过每次都有种“还是老伙计靠谱”的感觉。希望你也能把它变成自己的熟练工具而不是躺在笔记本里吃灰。