1. 这道题到底在问什么从网络延迟时间说起经典图论题“网络延迟时间”某知名在线评测系统的第743题看起来是一道标准单源最短路径题但很多人不知道用 Floyd 弗洛伊德算法也能非常优雅地解决而且代码量比 Dijkstra 还少。我第一次做这道题时第一反应是用 Dijkstra后来看了一眼数据范围发现 n 最大只有 100果断改用 Floyd三分钟写完就过了。先把题目翻译成人话有 n 个网络节点节点间有若干条有向边每条边有一个传播延迟时间。现在从某个源节点 k 发出一个信号信号可以同时沿着多条路径传播问所有节点都收到信号一共需要多久。如果有节点永远收不到信号直接返回 -1。很多人会在这里卡一下“所有节点都收到需要多久”到底怎么算其实信号是并行传播的某个节点收到信号的最早时间就是从源点到这个点的最短路径长度。而最后一个节点收到信号的时间就是所有节点最短路径里的最大值。所以答案就是先求源点 k 到每个节点的最短路径再取这些路径里面的最大值存在不可达节点时返回 -1。换句话说这是一道伪装成“网络题”的纯图论最短路题。Dijkstra 当然能解但既然 n 只有 100全网最省脑细胞的 Floyd 算法完全有资格上场。接下来我会先拆解 Floyd 的核心原理再给出完整的 743 解法最后聊聊那些教程里常忽略的坑。2. Floyd 算法核心原理拆解2.1 动态规划视角从三维状态到二维滚动数组Floyd 算法的本质是动态规划不是简单的“三重循环暴力”。它解决的问题是任意两点 i 到 j 的最短路径长度。Floyd 的核心思想是逐步开放“中间节点”。一开始我们只允许路径不经过任何中间节点也就是 i 和 j 直接相连距离就是边的权重不直接相连就是无穷大。然后我们允许路径经过节点 0看看能不能通过 0 绕一下让距离更短。接着允许经过节点 0 和 1再接着 0、1、2……直到允许经过所有节点。用状态表示就是d[k][i][j]表示“从 i 到 j且中间只允许经过前 k 个节点编号 0 到 k-1时”的最短距离。递推式长这样d[k][i][j] min(d[k-1][i][j], d[k-1][i][k-1] d[k-1][k-1][j])这个递推式的含义很直观对于新开放的中间节点 k-1要么不通过它那就保持原样要么通过它那路径就拆成i - k-1和k-1 - j两段。两种情况取较小值。状态数组第一维是“允许经过的节点集合范围”这一维可以滚动掉因为每一次更新只依赖上一轮的结果。所以常见的二维写法是for k in range(n): for i in range(n): for j in range(n): dist[i][j] min(dist[i][j], dist[i][k] dist[k][j])dist[i][j]最终就是 i 到 j 经过所有中间节点后的最短路径长度。这里有一个很多人没想明白的点为什么滚动数组更新后结果还是对的理论上dist[i][k]和dist[k][j]可能已经在当前 k 轮被更新过了那不就是用了“未来”的状态吗实际上不会错。原因在于从 i 到 k 的最短路径即便允许经过 k也完全不需要真的把 k 作为中间节点否则就形成一个经过 k 的环在正权图里这种环只会让路径变长。所以i - k的最短路径在开放 k 之前就已经确定了滚动数组当场更新正好保持正确性。这个细节搞明白之后Floyd 就不再是死记硬背的三重循环了。2.2 循环顺序为什么必须是 k 在外层Floyd 最容易写错的地方就是把k循环放在最内层比如写成for i in range(n): for j in range(n): for k in range(n): dist[i][j] min(dist[i][j], dist[i][k] dist[k][j])这样看着好像“遍历每个点作为中转”实际上结果是错的。原因在于状态转移的顺序被破坏了。二维滚动数组要求“当前 k 轮的结果必须建立在上一轮结果基础上”。如果把 i 和 j 放外层那么内层每换一个 kdist[i][j]都会基于一组不完整、混着不同“允许节点集合”的值来更新。这就好比盖房子砖还没干就急着往上砌最后整面墙都会塌。所以 Floyd 循环顺序的硬性规定是中间节点 k 在最外层起点 i 在中层终点 j 在最内层。这个顺序不能改改了答案就会错。实际写代码时还建议给这个变量取名mid不要和题目里的源节点k混在一起不然很容易把自己绕晕。3. 用 Floyd 解决 743 的完整过程3.1 邻接矩阵初始化与数据预处理Floyd 用邻接矩阵存储最方便。题目里的节点编号是 1 到 n而数组下标习惯从 0 开始所以做一次u-1、v-1转换。初始化的要点有三个矩阵所有位置初始化为一个很大的数 INF表示“暂时不可达”。每个节点到自己的距离初始化为 0。每读入一条有向边(u, v, w)就执行dist[u-1][v-1] min(dist[u-1][v-1], w)。为什么要对每条边取min因为题目数据里可能存在重边。虽然 743 原题通常不会刻意给重边但拿这个模板去刷其他图论题时重边很常见。如果不取最小值后读入的较大权重会把较小平权覆盖掉最短路结果就错了。这种“习惯性防御”能帮你少踩坑。自环也不用特殊处理先初始化对角线为 0再更新边权时min(0, w)必然是 0正权自环不会污染答案。3.2 核心 Floyd 实现与逐行说明完整的 Python 解法如下from typing import List class Solution: def networkDelayTime(self, times: List[List[int]], n: int, k: int) - int: INF 10 ** 9 dist [[INF] * n for _ in range(n)] # 每个节点到自身距离是 0 for i in range(n): dist[i][i] 0 # 读入边节点编号从 1 开始转为 0 开始 for u, v, w in times: dist[u - 1][v - 1] min(dist[u - 1][v - 1], w) # Floyd 三重循环 for mid in range(n): for i in range(n): if dist[i][mid] INF: continue for j in range(n): nd dist[i][mid] dist[mid][j] if nd dist[i][j]: dist[i][j] nd # 求源点 k 到所有节点的最大最短路径 source k - 1 ans 0 for i in range(n): if dist[source][i] INF: return -1 ans max(ans, dist[source][i]) return ans代码逻辑并不复杂。mid是当前允许作为中转的节点i是起点j是终点。nd dist[i][mid] dist[mid][j]是“从 i 到 mid再从 mid 到 j”的候选距离。如果候选距离比当前记录短就更新当前记录。中间加了一个小优化if dist[i][mid] INF: continue。如果起点 i 到中转点 mid 本身不可达那无论 j 是什么都不可能通过 mid 到达这轮直接跳过。这个优化不改变正确性只是省掉一部分无效加法。在 n100 的时候无所谓但当成模板写下来也不亏。这里也顺便回应一个疑问如果dist[i][mid]是 INF而dist[mid][j]是负数会不会出现INF 负数小于 INF 导致误更新的情况不会。INF 只是一个“足够大”的数并不真的是无穷大所以从理论上说INF 负数确实可能小于 INF。但 743 的边权都是正数不存在这个问题。如果哪天遇到负权边建议直接用if dist[i][mid] INF: continue这种跳过方式从根上避开“假无穷”参与运算。3.3 答案提取max、INF 与 -1 的边界处理Floyd 跑完之后dist[source][i]已经是源点 k 到节点 i 的最短延迟时间。接下来要做的不是求和也不是求最小而是求最大值。为什么是最大值因为所有节点是同时开始传播的。举一个现实中的类比领导在群里发消息每个人各自收到消息的时间取决于网络状况但“群里所有人都看到消息”这个事件只能以最后那个收到的人才算完成。把“最慢的那个人”的时间取出来就是题目的答案。代码里有一个很容易忽略的边界如果某个dist[source][i]还是 INF说明这个节点根本不可达直接返回 -1。注意判断时机需要在累加最大值之前一旦发现不可达整个网络就不满足“所有节点都收到信号”的要求。还有一个隐藏边界当 n 1 时只有源点自己dist[0][0] 0max 取出来是 0代码会正确返回 0。这时候 times 列表大概率是空的循环直接跳过但初始化部分已经把对角线清零所以不会出错。4. 复杂度分析与最短路算法横向对比4.1 时间与空间复杂度Floyd 的时间复杂度是 O(n^3)。在 n 100 的情况下核心循环只有 100 的三次方也就是 100 万次操作。这个量级在 Python、Java、C 里都是轻轻松松提交完全不会超时。空间复杂度是 O(n^2)因为只要维护一个 n x n 的邻接矩阵。100 乘以 100 的二维数组内存占用几乎是零。就算 n 到 300Floyd 也还能拼一拼到 500 时 O(125000000) 就会开始吃力了。所以 743 选 Floyd本质上是数据范围给的底气。不过要注意Floyd 的时间复杂度里其实还应该加上读取边时的 O(m)。m 在 743 里最多是 6000不影响大局但在分析复杂度时不要漏掉。4.2 Dijkstra、Bellman-Ford、Floyd 到底怎么选很多同学看到“最短路”就直接背 Dijkstra这当然没错但不能只会一种。三种算法各有用武之地我用一张表整理清楚算法求解目标时间复杂度支持负权边适用场景Dijkstra单源到所有点O(m log n) 或 O(n^2)不支持稀疏图、大图、正权边Bellman-Ford单源到所有点O(n * m)支持负权边、需要检测负环Floyd所有点到所有点O(n^3)支持无负环点少、多源最短路回到 743它要的是单源最短路所以教科书标准解法是 Dijkstra。先用邻接表建图再用优先队列维护“当前距离最小的节点”不断松弛邻居。Dijkstra 的复杂度在 m 6000 时大概是几万次堆操作理论上更快。但我个人在实战里经常选 Floyd理由是“代码零思考”。Dijkstra 需要考虑邻接表、visited 数组、优先队列、重边处理稍不留神就写错。Floyd 就是无脑三重循环初始化好矩阵剩下的交给 DP。对于 n100 的小图Floyd 比 Dijkstra 更不容易出错也更适合面试时手写。如果在竞赛里遇到 n 很大但边很少的图不要用 Floyd老老实实堆优化 Dijkstra如果题目里有负权边Dijkstra 直接失效负权且无负环时优先 Bellman-Ford负环需要判断则 Bellman-Ford 也可以只有当你需要任意两点的最短路或者图非常小、想快速出题时Floyd 才是最优解。5. 实操中的经验与坑5.1 INF 的取值一个能把人坑哭的细节INF 的选择是 Floyd 新手最容易翻车的地方之一。有人喜欢用Integer.MAX_VALUE在 Java/C 里然后在更新时直接写dist[i][j] min(dist[i][j], dist[i][mid] dist[mid][j])。问题来了两个很大的数相加会溢出成负数min 一比较负的反而更小于是真的把路径改成一条“负无穷瞎路径”整个矩阵被污染。正确的做法是选一个“足够大但相加不溢出”的数。比如 C 里可以用1e9Python 里用10 ** 9。如果题目的最大边权和路径长度都远超这个值那就用long long并用更大一点的 INF。更稳妥的写法是像前面代码那样先判断dist[i][mid] INF就直接 continue不让 INF 参与加法从根源上减少溢出的可能。5.2 重边、自环、节点编号转换这些 corner case我先说重边。题目没说没有重边你的代码就要当它有。邻接矩阵初始化后每次读入边都取min这才是正确姿势。如果直接赋值dist[u][v] w遇到一条较大的同向边会把原来的小权重顶掉输出就会偏大。再说自环。自环对最短路没有正面贡献但初始化不当时会污染答案。例如有个节点 1 有一条1 - 1的边权重是 5如果初始化对角线不是 0 而是 INF那么这条边会把dist[0][0]更新成 5最后答案 max 就变成了 5而不是 0。所以务必先在循环里把dist[i][i] 0设置好。最后是编号转换。743 的输入节点是从 1 开始编号的数组是从 0 开始。忘记减一会导致越界或者逻辑错乱。很多同学在本地测试时手贱把数据改成 0 开始提交时忘了还原结果整体偏移一位异常难排查。建议代码里统一规定读入边后立刻u - 1; v - 1源节点也k - 1后续不再混用。5.3 循环变量命名与调试建议前面提过Floyd 的中转循环变量如果也叫k会和题目里的源节点k冲突。在 743 里源节点参数就是k如果再写for k in range(n)不仅覆盖了源点还会让自己看代码时一头雾水。我在重写这题时特意把中转点命名为mid源点转成source整个人都清爽了。调试 Floyd 还有一个实用技巧如果觉得答案不对先打印dist矩阵重点看三个地方。对角线是否为 0直接相连的边是否和输入一致某个dist[i][j]是否比两个直接跳转路径更长。这三项没问题说明初始化正确再检查循环顺序基本都能定位到问题。5.4 提交实测与个人习惯我自己在写这题时最初是打算用 Dijkstra 的结果写了一会儿发现要处理优先队列重载、visited 去重、邻接表初始化一下没刹住就写复杂了。后来看到 n 上限 100直接把代码删掉重写成 Floyd提交一次过。这并不是说 Dijkstra 不好而是我们要养成“先看数据范围再选算法”的习惯。n 100就是 Floyd 的舒适区n 1000就得认真考虑 Dijkstra 了n 10000基本只能 Dijkstra 或 Bellman-Ford 级别的算法。算法是为数据服务的不是越“高级”越好。最后分享一个我自己的小习惯遇到最短路题目我会先在草稿纸上写一下期望复杂度。100^3 1000000这个量级我默认可以接受500^3 125000000Python 就会有点悬。如果你能提前算这一步很多超时问题其实根本不会发生。743 这道题用 Floyd就是我在数据范围面前做出的最优选择。