入门图论最短路LeetCode 743 是一道绕不开的题。题目名字叫“网络延迟时间”核心是给你一个有向带权图让你算从某个源点 K 发出信号信号传遍所有节点需要的最短时间。如果存在不可达节点就返回 -1。这道题本质上是一个“单源最短路径”问题而且边权全部为正所以经典的 Dijkstra 算法是解它的最优选择之一。适合正在学图论、准备算法面试、或者想系统梳理最短路算法适用边界的读者我把从建图、算法选型、剪枝细节到边界 case 的坑完整拆一遍。1. 整体设计与思路拆解为什么一看到这题就要想到 Dijkstra1.1 题目在说什么怎么把它翻译成图模型题目里给了一个 n 表示节点总数节点从 1 到 n 编号。times 是一个二维数组其中 times[i] [u, v, w]表示从节点 u 到节点 v 的单向边传播时间是 w。K 是信号发出的起点。我们需要计算从 K 点发出信号后所有节点都收到信号需要的时间。这个描述翻译成图的语言非常直观节点就是网络中的路由器或者主机有向边表示一条单向通信链路边权就是时延。信号从 K 出发沿着链路同步向周围扩散。这里有个关键点值得注意——网络中信号的“同步扩散”和算法里“单源最短路”为什么是等价的。因为信号每到一个节点后会同时向这个节点的所有出边继续传播所以某个节点第一次收到信号的时刻就恰好是从 K 到这个节点的最短路径长度。你不需要关心信号是经过了哪些中间节点绕过来的只需要关心最早到达的时间。当所有节点都收到信号这个“全局完成时间”一定是 K 到所有节点最短距离里的最大值也就是 max(dist[i])其中 i 遍历所有节点。所以在代码实现层面任务就变成先建图然后算出 K 到每个节点的最短距离最后遍历一遍距离数组取最大值。任何“某个节点无法到达”的情况对应到算法结果就是 dist[i] 仍然是初始化的正无穷。如果遍历时发现还有正无穷函数直接返回 -1。1.2 为什么这道题是 Dijkstra 的主场而不是 BFS 或别的算法接触过 BFS 的同学可能会问这场景不是跟“广播风暴”很像吗为什么不能直接用 BFS 逐层扩散原因在于 BFS 默认每走一步的代价相同在无权图里 BFS 确实就是最短路算法。但 743 题里的边权 w 每个节点之间不同范围可以从 1 到 100 不等BFS 按层扩散算出来的路径长度与真实时延不对应。再看为什么不用动态规划或者纯贪心秒杀。最短路问题如果存在负权边就会很麻烦因为负权会让“当前已选路径最短”这个贪心假设失效。而这题题目明确所有 w 都是正数一个正权有向图天然适合 Dijkstra 使用的贪心策略每次从尚未确定最短距离的候选节点中挑出当前距离最小的节点然后尝试通过这个节点刷新它的所有邻居。因为边权为正一个节点一旦被选出它的距离就不可能被后续节点再优化得更小。这类题的参考实现也有多种朴素 Dijkstra 复杂度 O(n²)适合节点数不多但边很密的图堆优化 Dijkstra 复杂度 O((nm)log n)适合边比较稀疏的图。743 里 n 最大到 100times 长度最多 6000两种写法都能轻松通过。但从算法能力训练的角度建议至少把两种实现都写过一遍这样才能理解贪心策略落地时对数据结构的依赖。1.3 我理解的出题人意图这道题被归为 Medium难度其实不算高但特别适合考察基础建模能力。我在面试和刷题群里见过很多次讨论发现一个现象很多人一看到“网络延迟”“信号传播”这种带实际场景描述的题目容易往模拟、BFS 方向钻实际上出题人考的就是能否把题面剥开识别出“在所有边权为正的条件下求解单源最短路”这个核心诉求。一旦这一步做出来后面选堆优化还是朴素实现都是顺理成章的事。做一个简单的对比就能看明白候选算法适用前提时间复杂度能否解决本题BFS无权图边权相等O(nm)否Dijkstra边权非负O((nm)log n) 或 O(n²)是Bellman-Ford可处理负权边O(n*m)能但浪费SPFA一般为正权负权也能跑期望 O(km)能但没必要Floyd多源最短路O(n³)大材小用单源点、正权图、最大只有 100 个节点——Dijkstra 几乎是为这道题量身定做的。后面我会先把最通用的堆优化实现全过程写透再把朴素思路和变种实现一并交代。2. 核心细节解析建图方式、距离数组与优先队列关键词2.1 如何高效地把 times 数组变成可用的邻接表写 Dijkstra 之前第一步是建图。图建立得好不好直接影响后续邻居遍历时写代码的顺手程度。在 743 这种题里我强烈建议使用邻接表而不是邻接矩阵。原因有三点第一邻接表只存真实存在的边遍历节点邻居时不需要扫描 n 个位点去判断哪个有边代码更简洁。第二复杂度更贴近真实边数堆优化 Dijkstra 里松弛操作只会对每条边执行有限几次邻接表能确保这一点干净体现。第三这道题的边数 m 最大 6000n 最大 100邻接矩阵 100×100 其实也不大但如果扩展这题的思路到大数据集邻接表习惯越早养成越好。Python 里建邻接表最自然的方式是from collections import defaultdict graph [[] for _ in range(n 1)] for u, v, w in times: graph[u].append((v, w))这里注意节点编号从 1 开始数组长度要留出 n1把下标 0 空出来。如果直接用长度 n 的数组后面遍历到节点 n 时就会越界十秒钟能让代码崩掉我在笔试时踩过这种低级坑。有些语言习惯里还有用字典套列表的比如defaultdict(list)也可以。但在 n 固定的情况下预分配列表更快也省去 key 判断。后续遍历某个节点邻居时直接写for neighbor, weight in graph[node]:即可。2.2 初始化数组的距离语义要清晰Dijkstra 的三个基本数据结构分别是dist 数组记录源点到所有节点的当前最短距离visited 数组或者叫 finalized 集合记录已经确定最短路的节点小根堆负责存储候选节点及其当前累计距离。初始化时源点的距离一定是 0其余所有节点的距离应该是无穷大。Python 里可以用float(inf)也可以用一个大数比如10**18。我在做题时更推荐10**9或float(inf)因为后面判断是否可达时可以直接比较if dist[i] float(inf)语义很清楚。不要用-1或0表示未访问这样会和真实边权混淆。还有一个值得注意的初始化细节堆里最初应该放入什么朴素想法是先把所有节点放进去权重初始无穷但标准做法是只放入源点 (0, K)然后让算法一步步把新节点推入堆中。如果把所有节点一股脑放进堆那和小根堆贪心选最小节点这个思路会绕弯而且堆中可能残留大量无效状态。只放源点更贴近 Dijkstra 扩展过程的核心思想。题外话如果写的是 Java 版本可以用PriorityQueueint[] pq new PriorityQueue(Comparator.comparingInt(a - a[0]));如果是 C就是priority_queuepairint,int, vectorpairint,int, greater pq;。语言不同但套路完全一致。2.3 贪心选择与松弛操作的前后顺序Dijkstra 主循环的标准形态是只要堆不空就弹出堆顶元素。假设堆顶元素是 (d, u)表示当前走到 u 点累计距离 d。这里有一个很关键的防御性判断如果 d 大于 dist[u]说明这个堆顶元素是先前某次松弛残留的旧记录可以直接丢弃不用处理。有人会问为什么要丢弃因为同一个节点可能被多条不同路径访问到每次发现更短距离时都会插入堆中所以堆里可能同时存在同一个节点多个不同距离的记录。如果不做判断可能把旧的大距离当成当前最优去扩展邻居导致错误答案。如果不做这个判断理论上把所有记录都处理完也能得到正确答案但会平白多出很多无效操作复杂度也不再干净。通过防御性判断之后说明当前 d 就是 u 点最终最短距离接着把 u 标记为 finalized即 visited 为 True再遍历 u 的每个邻居尝试通过“u 到 v”的路径刷新 v 的距离if d weight dist[v]: dist[v] d weight heapq.heappush(pq, (dist[v], v))这里一行if就是一个完整的“松弛操作”。你只需要记得 Dijkstra 的核心就是不断“选出当前最小候选”然后“用这个候选刷新它的邻居”循环往复直到所有可达节点都 finalized。2.4 visited 数组要不要很多讲解 Dijkstra 的伪代码里会用 visited 数组配合 dist 数组。在主循环里如果当前弹出的节点 v 已经被访问过直接 continue防止重复弹出造成死循环。但在用堆优化版本实现了上面说的“堆中旧记录防御性跳过”后visited 数组其实不是必需的。因为在正权图中一个节点一旦被作为最小距离弹出它不会再被一个更小的候选距离刷新后面旧的较大距离弹出时会被 d dist[u] 直接拦掉。话虽如此初学者我建议还是加上 visited。它能让逻辑更直观特别是当你之后试图改写 SPFA、Dijkstra 变种或处理更复杂约束时visited 的语义会越来越重要。多一个布尔数组开销基本可忽略却能把“节点真正被确定”这个步骤显式化不容易在调试时绕晕。3. 实操与代码实现三种写法的完整过程3.1 堆优化 Dijkstra工程上最实用的形态堆优化 Dijkstra 是面试中最推荐的答案因为代码扩展性好时空复杂度是标准的 O((nm)log n)而且写熟练了整个模板只需要 3 分钟。下面给出一个可直接运行的完整解法import heapq from typing import List class Solution: def networkDelayTime(self, times: List[List[int]], n: int, k: int) - int: graph [[] for _ in range(n 1)] for u, v, w in times: graph[u].append((v, w)) INF float(inf) dist [INF] * (n 1) dist[k] 0 pq [(0, k)] visited [False] * (n 1) while pq: d, u heapq.heappop(pq) if visited[u]: continue visited[u] True for v, w in graph[u]: if d w dist[v]: dist[v] d w heapq.heappush(pq, (dist[v], v)) max_delay max(dist[1:]) return -1 if max_delay INF else max_delay如果你用了 visited 数组那些旧的、更长的堆记录会在弹出时被跳过。注意这里我加不加if d dist[u]: continue都不影响正确性因为 visited 已经挡了一道。这是最稳妥的写法直接提交可通过所有 case。可能有同学觉得 visited 在这里其实没太必要因为 dist 的防御已经够用。实际工程代码两种都有重点是你得清楚自己依赖的是哪一层防护。我见过很多人把两种防线混在一起写结果代码逻辑看不出主次调试时反而分不清状态。我的建议是选一种你理解最深的防御方式另一种想留就留但心里要有数。3.2 朴素 Dijkstra理解 O(n²) 过程能帮你补足原理堆优化的代码本身并不难但如果你只写过堆优化版本对 Dijkstra 贪心过程的理解可能不够“贴肉”。所以建议老老实实实现一次朴素版class Solution: def networkDelayTime(self, times: List[List[int]], n: int, k: int) - int: # 邻接矩阵形式 graph [[float(inf)] * (n 1) for _ in range(n 1)] for u, v, w in times: graph[u][v] w dist [float(inf)] * (n 1) dist[k] 0 visited [False] * (n 1) for _ in range(n): # 从未访问节点中找到当前距离最小的 u -1 min_d float(inf) for i in range(1, n 1): if not visited[i] and dist[i] min_d: min_d dist[i] u i if u -1: break # 没有可达节点了提前结束 visited[u] True for v in range(1, n 1): if not visited[v] and graph[u][v] float(inf): new_d dist[u] graph[u][v] if new_d dist[v]: dist[v] new_d ans max(dist[1:]) return -1 if ans float(inf) else ans这段代码每轮都要扫一遍全节点找最小值内层又扫描所有可能的邻居所以复杂度是 O(n²)。对于 n100 的 743 题来说毫无压力。朴素版的好处在于它把 Dijkstra 每一步都展示得非常直白选点、标记、更新。当理解了这个流程之后堆优化相当于是把“找最小距离节点”这一步拿小根堆做了一把优化核心贪心逻辑并没有任何改变。利用邻接矩阵会不会浪费空间在 n100 的情况下不会。但若你未来在处理 n 很大且稀疏的图这种 O(n²) 的模版绝对会超时所以你必须知道什么时候能用朴素版什么时候必须用堆优化版。3.3 Bellman-Ford 和 SPFA给探索者的一条支线虽然 743 的最优解属于 Dijkstra但如果想对最短路算法形成体系强烈建议把 Bellman-Ford 也实现一遍。这会在未来遇到含负权边的题时让你不至于束手无策。题目本身不要求但作为刷题拓展意义挺大。Bellman-Ford 的思路非常暴力对所有边进行 n-1 轮松弛。因为一条最短路径最多经过 n-1 条边所以松弛 n-1 轮后必然收敛没有负环时。如果第 n 轮还能松弛说明图中存在负环。class Solution: def networkDelayTime(self, times: List[List[int]], n: int, k: int) - int: INF float(inf) dist [INF] * (n 1) dist[k] 0 for _ in range(n - 1): changed False for u, v, w in times: if dist[u] ! INF and dist[u] w dist[v]: dist[v] dist[u] w changed True if not changed: break ans max(dist[1:]) return -1 if ans INF else ans而 SPFA 是对 Bellman-Ford 的一种队列优化。维护一个队列只有被松弛过的节点才可能引发邻居的进一步松弛。用在这题虽然可行但在“正权图”的题里跑 SPFA本质上是把 Dijkstra 能更优雅完成的事情复杂化了一点所以更像教学演示。from collections import deque class Solution: def networkDelayTime(self, times: List[List[int]], n: int, k: int) - int: graph [[] for _ in range(n 1)] for u, v, w in times: graph[u].append((v, w)) INF float(inf) dist [INF] * (n 1) dist[k] 0 in_queue [False] * (n 1) q deque([k]) in_queue[k] True while q: u q.popleft() in_queue[u] False for v, w in graph[u]: if dist[u] w dist[v]: dist[v] dist[u] w if not in_queue[v]: q.append(v) in_queue[v] True ans max(dist[1:]) return -1 if ans INF else ansSPFA 在极端构造下复杂度可以退化到 O(n*m)。竞赛圈里偶尔有人用 SPFA 跑正权图拿 AC但在面试机试里我不会首选它因为算法题面试官期望的是你能说清 Dijkstra 的贪心依据。SPFA 更适合作为调研对比项出现在你脑中而不是作为标准答案直接写在 743 的题解里。3.4 三种解法的取舍从工程与面试角度谈如果你在准备面试标准答案就写堆优化 Dijkstra同时能口述朴素 Dijkstra 的原理代码里体现邻接表建图、堆取最小值、松弛三层结构这已经足够。如果时间充裕可以用 Bellman-Ford 对比说明为什么 Dijkstra 不适用于负权边再顺手提一嘴 SPFA 的不稳定性面试官会觉得你的知识面是成体系的而不只是背了个模板。从工程落地角度看真实网络中计算链路时延几乎不会出现负权边所以 Dijkstra 就是现代链路状态路由协议如 OSPF里最短路计算的基石。做这道题的意义不止于通关它能帮你在将来阅读路由协议相关源码时清楚知道“路由器刷新的 LSDB 链路状态数据库 SPF 计算”到底在算什么。4. 常见问题、边界 case 与避坑实录4.1 返回值为什么不是累加路径长度而是最大距离这一点几乎每个初写这道题的人都要卡一下。题面问的是“所有节点收到信号所需时间”。由于信号是并行传播的不同分支路径是同时走的因此整个网络全部收到信号的耗时等于最慢那条最短路径的长度。这也就是为什么代码里最后取max(dist[1:])而不是把所有距离相加。用生活中例子类比在办公室群里发一条全员通知你在群里 所有人人力同学 5 分钟看完、技术同学 10 分钟后看完而不是等所有人看完的时间叠加成 15 分钟。公司全员收到消息的时间是 10 分钟最慢者其它人收到也不影响这个最大值因为所有链路并行传播。理解了这个代码就不用纠结了。4.2 节点从 1 开始标记dist 数组下标别搞错题目里 n 个节点编号从 1 到 n不是 0 到 n-1。这是 LeetCode 图论题中比较常见的出题习惯。你可以在建图时直接用 n1 长度的数组把下标 0 空置最大节点编号 n 能直接落在dist[n]上。如果不这么做而是用 n 长度数组并自行做u-1、v-1转换代码也能过但平添一层心智负担。尤其是面试现场时间紧张少一层坐标转换就少一撮 bug 风险。计算最终答案时使用max(dist[1:])注意这个切片刚好把下标 0 排除在外不会把多余的 inf 带进来。如果你用max(dist)而 dist[0] 也是 inf那在有不可达节点时会得到 inf但如果你用 -1 处理返回值时就会把一切正常节点也当成不可达。提前在任何边界写清楚下标这个细节运行结果会干净很多。4.3 堆里残留的旧记录要不要处理堆优化 Dijkstra 中同个节点可能被压入堆多次先压一个距离为 10 的记录后来又发现距离为 6 的路径于是又压入一个 (6, node)。小根堆会自动让 (6, node) 先弹出。等到 (10, node) 弹出时如果这个节点已经被 finalized或 dist[node]6 而 d10 dist[node]就直接跳过。这是一个非常重要的工程细节。如果不跳过旧记录那个旧记录会重新触发对节点邻居的松弛操作虽然由于d w dist[v]往往无法刷新不至于错误但会让很多节点被重复试跳浪费大量时间。理论上会把 O((nm)log n) 退化到 O(m log m)也未离谱但一旦有人误以为每个节点只处理一次写出的统计或剪枝逻辑就会不对。刷题时直接按模板跳过即可。4.4 孤立节点与不可达节点同时存在怎么处理假设 n5其中节点 5 没有任何边入度、也没有任何路径从 K 能到那么它的 dist 留在 inf。遍历取最大值时如果算法只是单纯取最大值结果会是 inf最终返回 -1。这是正确行为。但如果题目改成“至少有一个不可达节点时返回 -1”你的实现不必提前把孤立节点排查出来让 Dijkstra 跑完看最终最大距离是否仍为 inf 就行。不过有一点要提醒如果你使用提前结束优化的朴素版比如在选点阶段发现所有未访问节点距离都为 inf 就 break那最终结果里 inf 依然保留所以结果仍然正确。不要在 break 后直接返回 0 或某个局部最大值那样会把不可达节点漏掉。4.5 自环和重边会不会影响结果信号传输不可能从某个节点出发经过 0 秒再回到自身自环通常并没有意义。如果 times 里出现了 u v 的边Dijkstra 在遍历邻居时dist[u] w dist[u]是不可能成立的因为 w 不小于 0所以不会影响结果。但这提醒我们建图时不需要刻意去重也不会因重边出错不过如果多次不同权重的重边中有一条更短松弛时会自动采用最短的那条这完全符合 Dijkstra 的预期。换句话说重边自环可以留着不管。4.6 如果 n 很大且 times 很大怎么办743 题的规模非常友好n 只有 100。但如果面试官临时扩展问“n 变成 10^5边数 2×10^5 呢”你要答出堆优化 Dijkstra 仍是第一选择时间复杂度 O((nm)log n) 大概能跑在几十到几百毫秒级别。朴素版 O(n²) 会直接爆掉所以你在代码里应尽量写堆优化 Dijkstra 的模板。同时要留意 Python 的递归深度与此题无关因为 Dijkstra 是迭代解法不会遇到 recursion limit 问题。4.7 调试最短路题目的独门技巧如果你提交后样例没过可以用下面这套排查顺序快速定位问题第一打印 dist 最终数组看看到底是哪个节点距离不对第二只保留 dist 更新日志查看每个节点第一次被压入堆时的路径长度以及它的前驱节点是谁第三检查是不是把有向图当成无向图建图了。这个问题非常常见times 表示 u 到 v 的单向发射所以只在 graph[u] 中加入 v千万别在 graph[v] 中也加入 u。一旦误建为无向边很多原本不可达的节点会变成可达答案会跟预期完全不符。5. 顺着 743 想开去这类题还能怎么变着考5.1 把“求最大值”换成“求路径数量、最少跳数”如果此题改成K 发出信号要求统计信号能到达多少节点那 Dijkstra 跑完统计一下 dist 中 inf 以外的数量即可。如果改成“最少经过多少跳能到达所有节点”那这就是无权图最短路用 BFS 更合适BFS 层数天然就是最少跳数。大多数时候代码核心逻辑不变变的只是最后统计目标以及存储对象。这告诉我们一个刷题方法论尽量把题目拆成“建模 最短路模板 结果处理”三段。比如最后如果要求的是“所有节点都收到的最短时间超过阈值 T 则返回 -1”那无非是在取最大值前多一个阈值判断。模板本身稳定变通都在外层这样你考场发挥才能稳。5.2 从单源扩展到多源LeetCode 多源 BFS 题如果把源点从 1 个变多个例如多个信号源同时广播问多快能覆盖全部网络那最短路模型就变了。由于每个源点可能有一个独立的“出发时间”此时你需要一个虚拟超级源点将这个虚拟节点向所有真实源点连一条权重为 0 的边问题就又变回单源最短路。这种“超级源点”思想在算法题中很常用比如 多源 BFS、并查集连通性预处理、最小生成树的某些建图优化套路都很像。理解 743 之后再接触这些题目你会在建图阶段多一层“抽象”。你不只是把输入搬到邻接表里而是懂得主动增加虚拟节点来统一问题形式。这在我看来是刷题从“背板子”走向“会建模”的真正分水岭。5.3 真实网络里的网络延迟测量算法题里网络延迟是一个理想化的模型。真实网络里的 RTT往返时延通常用 Ping 命令测量网络拓扑是动态的存在拥塞、丢包、队头阻塞等各种复杂因素而不只是静态权重图。但这并不影响 Dijkstra 在真实路由协议中的地位比如 OSPF开放最短路径优先在区域内使用 SPF 算法计算路由核心思路就是 Dijkstra。假设你在公司内部自己搭了一个监控系统要把各机房间的延迟作为边的权值建图用于寻找控制面到数据面组件之间的最优路径那这题的思路直接可用。权值来源可以是历史的 ICMP 时延或者远端上报的 RTT建图后每次链路权重变化时重新计算一次最短路就能动态切换请求的转发路径。这类场景里“单源最短路径”只是更复杂路由算法的第一层地基。6. 总结一下实战经验用一次错题换来的三个教训最后说点实际做题体验。我自己第一次做 743 时误把信号传播当成“树形结构从根开始逐层叠加”上来就想用递归 visited 模拟扩散结果样例能过提交就因为在环状结构中无限递归而超时。后来老实把图建出来用 Dijkstra 三步走才稳定 AC。这个经历让我意识到一件事看见“网络”“广播”“延迟”这种名词第一反应不应该是试图模拟物理过程而应该审视其数学结构。如果你也在刷这道题我的建议很具体先把 743 的堆优化 Dijkstra 模板写熟再用朴素版实现验证一次自己的理解最后拿 Bellman-Ford 对照一下。一道题写三个最短路算法看起来像是在“绕远路”实际上是把 Dijkstra、Bellman-Ford、SPFA 三种套路一次焊进脑子里。以后遇到负权、多源、稠密图、稀疏图这些变种你都能条件反射般地选对工具。关于复杂度的记忆也有个小技巧不用死记 O(n²) / O((nm)log n)而是这样理解——Dijkstra 操作的核心是“找当前未确定点中距离最小的点”以及“遍历该点的邻居并松弛”朴素版找最小点是 O(n)做了 n 次所以多一组 n堆优化版利用优先队列让找最小点变成 O(log n)每次边松弛可能入堆一次所以有个 m 因子。理解了 n、m、log n 每个来源面试时随口推导出来绝对比背模板印象更深刻。如果你想要一道延伸题练手我建议做 LeetCode 787K 站中转内最便宜的航班它和 743 一样是有向带权图求最短路径但添加了“最多经过 K 站”的限制。这时 Dijkstra 需要改造成带状态的最短路或者直接用 Bellman-Ford 变种做完它你对最短路问题的理解又会深一层。写这篇东西也是想给正在刷题的人一个参照代码不需要背抓住建模和算法边界遇到新题也能根据图的性质选出正确解法。743 是经典的“一道入门多算法”的题目吃透它的性价比高到你无法忽视。
