刷 LeetCode 时碰到 743 这道网络延迟时间我猜你大概率已经搜到一堆解法文章了但多半都在推 Dijkstra 堆优化代码一坨细节一多新手很容易看懵。我今天想换个视角把这道题当成理解 Bellman-Ford 算法的绝佳标本来讲。很多人只把 Bellman-Ford 当成一个能处理负权边的冷门算法草草背完模板就放下其实它的松弛思想恰恰是理解所有单源最短路径算法的钥匙。743 的 N 和 E 规模都不大用 Bellman-Ford 来解代码短、逻辑直、边界少非常适合把算法原理完全吃透。这篇文章我会从题目分析讲到 Bellman-Ford 的核心原理再给出可直接运行的完整实现并且把我在实际调试中踩过的坑、面试中常被追问的选型问题、以及 Bellman-Ford 在工程中的延伸用法一次性说完。无论你是刚开始刷图论题还是准备面试想要一眼看穿这道题的多种解法这篇文章都值得花十分钟读完。1. 题目本质网络延迟时间到底在问什么1.1 把 LeetCode 743 拆成人话题目描述看起来像网络工程本质却非常纯粹。把信息翻译一下有 N 个节点编号从 1 到 N给定一个二维数组times其中times[i] [u, v, w]表示从节点 u 出发到节点 v 的耗时是 w这是一个有向边。现在从编号为 K 的节点发一个信号信号会沿着这些有向边不断扩散问你从 K 开始所有节点都能收到信号的最小时间是多少如果有节点永远收不到信号返回 -1。比如一个简单例子times [[2, 1, 1], [2, 3, 1], [3, 4, 1]] n 4 k 2信号从 2 出发。2 可以同时发信号给 1 和 3耗时都是 1。节点 3 在收到信号后继续发给 4又多花 1 秒。最后所有节点收到信号的时间是 2 秒。这个过程一抽象就是一张有向带权图K 是唯一的源点。每个节点收到信号的最早时间等于 K 到该节点的最短路径长度。而所有节点都收到信号的时间等于这些最短路径长度里的最大值。如果某个节点 K 根本到不了那它的最短路径就是无穷大此时答案是 -1。这里藏着一个容易被新手绕晕的认知点为什么要求最大值不是求和因为信号传播是并行的。信号从 K 出发后沿着不同边同时往外走而不是像送货一样必须一件一件依次完成。像群聊转发消息一样你同时发给两个人各自接收耗时不同所有人都已读这个事件只能由最慢的那个人决定。所以答案是所有节点的最短路取最大值不是把他们加起来。1.2 输入规模与 off-by-one 陷阱743 的数据范围我记得比较清楚N 最大是 100times长度最大是 6000权重 w 是非负整数。这个规模相当小意味着很多算法都能通过包括时间复杂度看起来有点吓人的 O(N * E) 的 Bellman-Ford。最坏情况下 99 轮乘以 6000 条边约 60 万次松弛在现在的机器上毫秒级就能跑完。真正值得警惕的是节点编号从 1 开始。如果你习惯性地开int[] dist new int[n]那么dist[k]在 k 等于 n 时直接数组越界。正确姿势是开n 1让下标 0 闲置只操作下标 1 到 N。另一个容易被忽视的点是题目给的是有向边。部分人做题时顺手把所有边建成了双向的想着信号应该能来回传结果在有向图用例上多算了可达路径答案偏小。判断自己有没有踩这个坑很简单如果某些测试用例答案比你手算的还小八成就是有向图写成无向图了。2. Bellman-Ford 算法原理最朴素的方案为什么既简单又可靠2.1 核心操作松弛Bellman-Ford 的全部逻辑就是一个动作松弛。给定一条有向边u - v权重为 w如果当前已知的源点到 u 的最短距离是dist[u]那么我们就尝试用dist[u] w去更新dist[v]。只要它比当前dist[v]更小就更新。为什么要叫松弛可以把dist[v]想象成一根原本绷得很紧的绳子。初始时我们不知道 v 怎么去所以dist[v]被设成无穷大绳子处于极度绷紧状态。松弛操作就是用一条实测可行的路径把这个紧绷的估计值慢慢放松到真实最短距离。单看一次松弛没什么了不起但把图上所有边都松弛一遍就完成了一轮信息扩散。每一轮扩散都会让已知的最短路径信息沿着边向外走一层。这就像在水面上投下一颗石子涟漪一层层往外扩散。第 1 轮扩散能覆盖走 1 条边能到的节点第 2 轮扩散能覆盖走 2 条边能到的节点以此类推。2.2 为什么只需要 n-1 轮循环这是理解 Bellman-Ford 最关键的地方几乎每次面试必问。假设图里有 n 个节点从源点 s 到任意节点 v 的最短路径最多包含多少条边答案n - 1 条。原因是如果一条路径出现了环那么在不存在负权环的前提下这个环只会让路径更长或者不改变长度0 权环。最短路径一定不会无缘无故绕一个环所以最短路径一定是简单路径最多经过 n 个节点边数最多 n - 1。由此就得到了 Bellman-Ford 的循环框架第 1 轮松弛后所有通过 1 条边就能从 s 到达的节点dist 被正确计算出来。第 2 轮松弛后所有通过不超过 2 条边就能到达的节点dist 被正确计算出来。第 k 轮松弛后所有通过不超过 k 条边就能到达的节点dist 被正确计算出来。因为任何最短路最多 n - 1 条边所以循环 n - 1 轮之后所有可达节点的最短路都已经确定。你可以在每轮开始记一个updated标志如果一整轮松弛下来没有任何更新说明信息已经传播完毕直接提前退出。这是非常实用的剪枝虽然不改变最坏复杂度但平均表现好不少。2.3 它的看家本领负权边与负权环为什么有了 Dijkstra 还需要 Bellman-Ford核心原因就是负权边。Dijkstra 的贪心策略建立在当前距离最小的节点已经确定最短路这一前提下。一旦存在负权边后续某条负边可能把之前认为已经确定的 dist 再次刷新变小Dijkstra 的贪心假设直接崩掉。我在另一篇文章里详细分析过 Dijkstra 的堆优化实现这里只强调一点Dijkstra 要求边权非负这不仅仅是一个实现细节而是算法正确性推导中不可缺失的环节。Bellman-Ford 没有这个限制因为它不依赖贪心顺序而是暴力的、多轮的全局枚举。无论负权边出现在哪一层只要给够 n - 1 轮它都会被正确处理。而负权环是另一个极端。假设存在一条环环上所有边权之和为负那沿着这个环一直绕路径总长度可以无限减小最短路径就没有定义。Bellman-Ford 提供了一个检测负权环的办法在完成 n - 1 轮正常松弛后再额外扫描一遍所有边。如果这一遍扫描仍然有 dist 能被更新就说明存在负权环。如何理解这件事正常我们知道所有最短路最多用 n - 1 条边而额外一轮还在更新说明某条路径用了 n 条边且比所有用少于 n 条边的路径都短这路径只能包含了一个负权环。我当时是手动模拟了一个三角形负环才彻底想通的这比死记结论有用得多。3. 直接撸代码用 Bellman-Ford 解 743 的完整实现3.1 Python 版本极简到只剩一个双重循环from typing import List def networkDelayTime(times: List[List[int]], n: int, k: int) - int: INF 10 ** 9 dist [INF] * (n 1) dist[k] 0 for _ in range(n - 1): updated False for u, v, w in times: if dist[u] INF: continue if dist[u] w dist[v]: dist[v] dist[u] w updated True if not updated: break ans max(dist[1:]) return -1 if ans INF else ans这段代码里值得逐行解释的细节很多。INF 10 ** 9这个值的选择有讲究。743 中单个权重最大不会很大最多 100 个节点时最坏情况下最短路最多 99 条边总长度大约是99 * 最大的w量级在 10 的 4 次方到 10 的 5 次方。用 10 的 9 次方作为无穷大完全够用。如果你设得太大在 C 或 Java 里做dist[u] w时可能出现整型溢出变成负数后面整个逻辑都乱了。Python 没有溢出问题但保持这个习惯没有坏处。dist[k] 0源点到自己的最短路径为 0这个初始化必须在所有循环之前完成。循环内部的continue当dist[u] INF说明当前源点还到达不了 u那么u - v这条边暂时无法提供任何有效信息应该跳过。如果不跳在 Java 里INF w仍是一个很大的数通常不会影响正确性但容易让思维混乱。我更建议保留这个跳过逻辑它的存在也让代码语义非常清楚松弛的前提是 u 已经可达。dist[1:]从下标 1 取到 n。如果有节点仍为 INF说明不可达答案返回 -1。3.2 Java 版本溢出处理是很多人的隐藏扣分点class Solution { public int networkDelayTime(int[][] times, int n, int k) { int INF Integer.MAX_VALUE / 2; int[] dist new int[n 1]; Arrays.fill(dist, INF); dist[k] 0; for (int round 0; round n - 1; round) { boolean updated false; for (int[] edge : times) { int u edge[0], v edge[1], w edge[2]; if (dist[u] INF) continue; if (dist[u] w dist[v]) { dist[v] dist[u] w; updated true; } } if (!updated) break; } int ans 0; for (int i 1; i n; i) { ans Math.max(ans, dist[i]); } return ans INF ? -1 : ans; } }Java 版本和 Python 完全同构唯一需要额外注意的是Integer.MAX_VALUE / 2。如果你直接用Integer.MAX_VALUE作为 INF那么在计算dist[u] w时一旦两者相加超过Integer.MAX_VALUE溢出就会让结果变成负数而这个负数会成功地通过dist[u] w dist[v]的比较把 dist[v] 污染成一个荒谬的小值算法瞬间废掉。使用Integer.MAX_VALUE / 2之后即使相加也远远不会溢出同时它仍然大得足以表示不可达。这个细节我在帮别人 review 代码时见过多次很多人挂在 743 的极端用例上最后排查半天原因就是 INF 设得太满。3.3 正确性证明用大白话把递推关系捋清楚很多人觉得算法证明枯燥但 Bellman-Ford 的证明比 Dijkstra 好懂用归纳法两步就说清了。假设第 t - 1 轮循环结束时dist[v]已经正确记录了所有从源点出发最多使用 t - 1 条边到达 v 的最短路径长度。看第 t 轮我们遍历所有边对于某条边u - v如果真实存在一条最短路径恰好使用 t 条边到达 v并且倒数第二个节点是 u那么去掉最后这条边之后从源点到 u 的路径只使用了 t - 1 条边。根据归纳假设这个值已经在上一轮被正确记录在dist[u]里。这一轮对它做松弛就会把这个使用 t 条边的最短路径考虑进去。因为任意最短路径最多使用 n - 1 条边所以在 n - 1 轮之后所有最短路都已经被正确计算算法结束。这个证明说穿了就是一句话每轮松弛都在已知的 t - 1 条边路径基础上向外扩展一条边。我建议你把这句话背下来面试时能很自然地讲出来比背模板强太多了。4. 算法选型743 为什么既能 Bellman-Ford 又能 Dijkstra4.1 两种算法的横评对比刷 743 的时候你会在题解区看到大量 Dijkstra 堆优化版本。很多人会困惑既然 Dijkstra 更快那学 Bellman-Ford 还有什么用我给出一个直观对比表维度Bellman-FordDijkstra堆优化时间复杂度O(N * E)O(E log V)边权限制允许负权边要求非负权边负权环检测支持不支持代码复杂度简单二重循环中等需要优先队列预剪枝能力可提前退出天然按距离出堆工程常用程度差分约束、路由协议导航、地图路径规划返回 743 本身N 最大 100E 最大 6000Bellman-Ford 最坏约 60 万次计算运行时间几乎可忽略。所以Bellman-Ford 过不了 743是个常见的误解。它本质是 O(N * E) 的复杂度而不是 O(N^3)只要 N 和 E 同量级它实际上非常快。真正需要对比的场景是稀疏大图。如果 N 非常大而 E 相对很小比如 N10 万、E20 万Dijkstra 堆优化的 O(E log V) 会明显胜出而 Bellman-Ford 的 O(N * E) 要跑到 200 亿次左右确实无法接受。所以 Bellman-Ford 更适合小图稠密图和带负权边的场景。4.2 面试中怎样表现出算法视野如果在面试中遇到这道题我建议你不要上来就埋头写代码而是先给一段简短的分析这是一道单源最短路径问题。给定了 N 和 E 的规模两种可行方案。其一是 Dijkstra用优先队列维护当前距离最小的节点时间复杂度 O(E log V)前提是边权非负本题条件完全满足。其二是 Bellman-Ford对所有边做 n-1 轮松弛时间复杂度 O(N*E)优势是允许负权边且能顺带检测负权环。本题规模很小两种方案都能通过。如果只选一种我会用 Dijkstra因为它在稀疏图上更高效但 Bellman-Ford 的松弛思想也很值得深入讨论。这样回答的好处在哪首先展示你掌握不止一种最短路径算法。其次你主动说清了 Dijkstra 的适用前提是边权非负这说明你理解算法边界而不是只会套模板。最后你引出了 Bellman-Ford 的独特能力面试官很可能顺着追问那 Bellman-Ford 为什么能处理负权边或者负权环怎么检测这些都是这篇文章里我们已经拆解过的内容你可以从容接招。4.3 那 Floyd-Warshall 呢还有一个常见问题Floyd-Warshall 能不能解 743能。Floyd-Warshall 是全源最短路径算法复杂度 O(N^3)。N100 时只有 100 万次操作完全能通过。但它是牛刀杀鸡而且无法直接利用我们只关心单源 K 出发这个信息。如果面试被问你可以说Floyd 虽然能解但复杂度偏高且没有利用单源特性所以通常会选 Bellman-Ford 或 Dijkstra。这样既体现了知识面也让选型理由更充分。5. 易错点与调试实录这些坑我基本都踩过5.1 高频错误清单第一dist 数组长度没开够。节点从 1 开始如果开new int[n]访问dist[n]会越界这是最典型的 off-by-one 错误。解法很统一直接开n 1然后无视下标 0。第二有向边当无向边处理。用邻接表时只加u - v一条边就可以了。如果你顺手加了反向边某些用例会得到偏小的答案。这种情况我会建议先检查建图逻辑而不是急着翻算法。第三松弛时没有判断dist[u] INF。虽然在 Python 下影响不大但如果你把 INF 设定为一个足够大的值INF w依然巨大不会比dist[v]更小。这个检查更像是语义上的要求写出来之后代码更好读也不会在语言差异下踩整型溢出的雷。第四最后求最大值时把下标 0 也算进去了。下标 0 是闲置项正常初始化后它可能是 INF如果你直接对dist全量求 max答案会被 INF 污染。正确做法是只遍历合法节点下标 1..N。第五updated剪枝位置写在了内层循环之后却忘了在每轮开始时重置。这个错误很隐蔽一旦某一轮没有任何更新剪枝生效但如果标志位没有正确重置后续循环永远不会再进入算法提前结束但结果还没算完。我的习惯是每轮开始前直接赋false内层一旦更新就赋true。5.2 用手工模拟一遍让原理自己现身理论说再多不如手动推一遍小例子。上文的示例times [[2, 1, 1], [2, 3, 1], [3, 4, 1]], n 4, k 2初始化dist [INF, INF, 0, INF, INF]下标 0 闲置。第 1 轮遍历三条边边2 - 1dist[2] 00 1 INF更新dist[1] 1边2 - 3dist[2] 0更新dist[3] 1边3 - 4dist[3]本轮刚被更新但我们要看本轮开始时刻的状态。诚实地说本实现按times顺序扫描dist[3]在前面已经被更新了所以确实能用1 1 2更新dist[4] 2这一轮结束后dist 变成[INF, 1, 0, 1, 2]。第 2 轮再次遍历三条边2 - 10 1 1不比dist[1]小无更新2 - 30 1 1不比dist[3]小无更新3 - 41 1 2不比dist[4]小无更新updated为 false提前退出。最后max(dist[1..4]) 2答案 2。你手工推一遍之后会发现所谓 n-1 轮松弛不是玄学而是一层一层把路径信息撑开直到无法继续撑开为止。5.3 边界用例速查表情形期望结果测试重点K 无法到达某个节点-1检查 INF 判断是否准确n 1 时0此时只有一个源点节点信号不需要传播时间存在重边取最短那条重边不影响正确性但可检验松弛逻辑K 出度为 0 且 n 1-1源点无法扩散到任何节点所有节点距离相等该距离值求最大值逻辑是否正确这个表是我刷图论题时积累下来的通用自测清单适合所有最短路径题不只是 743。6. 延伸一公里SPFA、负环检测与现实场景6.1 SPFA 是 Bellman-Ford 的队列优化版SPFA 全称是 Shortest Path Faster Algorithm本质上是 Bellman-Ford 的队列优化。它不再老老实实每轮扫描全部边而是用一个队列保存距离刚刚被更新可能继续影响出边邻居的节点。每次从队头取出一个节点只扫描它的出边并尝试松弛如果邻居被更新且不在队列中就把它重新入队。平均情况下 SPFA 的确比朴素 Bellman-Ford 快有些随机大图甚至可以逼近 O(E)。但它的最坏复杂度依然是 O(N * E)而且可以被专门构造的数据卡到指数级别。国内竞赛圈对 SPFA 的争议很大很多老选手已经把SPFA 已死挂在嘴边。我个人观点是在工程代码里我更倾向写 Bellman-Ford 或 Dijkstra稳定性优先但理解 SPFA 能帮助你把松弛传播在脑内建模成更动态的过程所以值得学不一定要用。6.2 负环检测在差分约束系统里的实战价值差分约束系统是一种有意思的建模方式。给定一组形如x_u - x_v w的不等式要求找出一组合法解。看似和最短路径八竿子打不着但它可以转换成图模型把节点编号当成变量下标把不等式x_u - x_v w理解为一条从 v 到 u、权重为 w 的有向边。然后在这个图上跑 Bellman-Ford 单源最短路如果检测到负权环说明不等式组之间产生了矛盾无解。我在某次做一个排课资源分配系统时就曾用这个思路把一堆时长上限容量约束扔进图模型用 Bellman-Ford 快速判断方案可行性。那一刻我才真正意识到刷题时想不明白的负环检测为什么有意义在现实问题里是能直接解决麻烦的。这也是我愿意花一整篇文章来讲 Bellman-Ford 的原因它的价值远远超过 743 这一道题。6.3 743 的常见变体面试官很喜欢在 743 基础上做小改动看看你是否真的理解了模型。把有向图改成无向图建图时把一条边当作两条有向边即可。如果返回 -1 的逻辑仍正常算法不变。改成求 K 到指定节点 T 的最短路不再求全局 max而是取dist[T]其他逻辑全部一样。新增多个信号源这是多源最短路可以建一个超级源点连接到所有信号源边权为 0然后照跑 Bellman-Ford。每个节点有额外的转发延迟可以把节点拆成入点和出点中间加一条表示自身延迟的边这个技巧在很多题目里都会用到。这些变体的核心都还是单源最短路径框架理解原题解法后迁移成本很低。7. 写在最后的一点个人体会我最初做 743 时也是跟着主流教程先写的 Dijkstra 堆优化代码还不短调试时花了不少时间。后来重新拾起 Bellman-Ford写下十几行核心逻辑就过掉题目那一刻我才发现松弛这个基础操作才是最短路径算法真正的灵魂。如果让我给正在刷图论的朋友一个建议不要只背模板把 Bellman-Ford 的 n-1 轮循环理念彻底吃透。你可以找一个 5 个节点以内的小图亲手把每一轮松弛后的 dist 数组变化写出来。这个过程看起来笨但它比任何花哨的题解都更容易帮你建立真实的算法直觉。最后送大家一个调试技巧遇到图算法题目出错时别急着看大数据用例也别急着改代码先构造一个极小图用手推一遍所有节点的 dist 变化错误会在推导过程中自己跳出来。祝各位刷题顺利别被 743 吓到。