LeetCode 743. 网络延迟时间
字数 3312 2025-12-03 21:17:10

LeetCode 743. 网络延迟时间

题目描述

有 n 个网络节点，标记为从 1 到 n。同时给你一个列表 times，列表中的每个元素是一个三元组 (u, v, w)，表示一条有向边。其中 u 是源节点，v 是目标节点，w 是一个信号从源节点传输到目标节点需要的时间。

现在，我们从某个给定的节点 k 发出一个信号。需要多久才能使所有节点都收到信号？如果无法使所有节点都收到信号，则返回 -1。

解题过程

这个问题的核心是：给定一个带权有向图和一个起点，我们需要找出从起点到所有其他节点的最短距离，然后取这些最短距离中的最大值。这个最大值就是信号传遍整个网络所需的最短时间。如果存在无法到达的节点，我们就返回 -1。这正是一个典型的单源最短路径问题。由于边的权重（时间）都是正数，我们可以使用著名的 Dijkstra 算法。

Dijkstra 算法的核心思想是贪心和广度优先搜索（BFS）的扩展。它每次都从"尚未确定最短路径的节点"中，选择一个距离起点最近的节点，然后通过这个节点来更新其邻居节点的距离。

让我们一步步来：

步骤一：构建图（邻接表）
我们首先需要将输入的 times 列表转换成一种方便我们快速查询的数据结构，最常用的是邻接表。

  • 我们可以使用一个字典（Map）或者一个列表的列表（List of Lists）。这里我们使用列表的列表，索引代表节点编号（注意题目节点从1开始，我们的索引0不用或对应节点1）。
  • graph[i] 存储的是从节点 i 可以直接到达的邻居节点以及所需的时间。具体来说，graph[i] 是一个由 (邻居节点, 时间) 组成的列表。

例子：假设 n=4, times = [[2,1,1], [2,3,1], [3,4,1]], k=2
我们构建的邻接表 graph 如下（索引0我们不用，从索引1开始）：

  • graph[1]: [] (节点1没有出边)
  • graph[2]: [(1, 1), (3, 1)] (从2可以到1，时间1；从2可以到3，时间1)
  • graph[3]: [(4, 1)] (从3可以到4，时间1)
  • graph[4]: [] (节点4没有出边)

步骤二：初始化数据结构
我们需要两个关键的数据结构：

  1. 距离数组（dist）：dist[i] 表示从起点 k 到节点 i 的当前已知的最短距离。初始时，我们将起点 k 到自己的距离设为 0 (dist[k] = 0)，因为自己到自己不需要时间。对于其他所有节点，因为一开始我们不知道距离是多少，所以先设为一个非常大的数（比如 Infinity 或 Integer.MAX_VALUE），表示"尚未到达"。

  2. 优先队列（最小堆，minHeap）：这个队列帮助我们快速找到"当前距离起点最近的未处理节点"。队列中的每个元素是 (从起点到该节点的当前最短距离, 节点编号)。我们总是从堆顶取出距离最小的节点进行处理。

接上例，起点 k=2。

  • 初始化 dist 数组：dist = [Inf, 0, Inf, Inf, Inf] (索引0无用，dist[1]对应节点1，dist[2]对应节点2（起点）...)
  • 初始化 minHeap：首先将起点 (0, 2) 加入堆中。

步骤三：执行 Dijkstra 算法
这是一个循环过程，只要优先队列不为空，我们就继续：

  1. 取出当前最近节点：从最小堆中弹出堆顶元素，我们得到 (currentTime, currentNode)，其中 currentTime 就是从起点 k 到 currentNode 的最终确定的最短距离。为什么是最终确定的？因为我们是基于贪心策略，所有比它短的路径都已经被处理过了，所以当前这个值不可能再被更小的值更新。

  2. 遍历邻居节点：查看当前节点 currentNode 的所有邻居。对于每一个邻居节点 nextNode 和它们之间的边权重（时间）time，我们进行以下计算：

    • 新的潜在距离 = currentTime + time
    • 如果这个新的潜在距离小于我们之前记录的到 nextNode 的距离 dist[nextNode]，说明我们找到了一条更短的路径。

  3. 更新距离和堆：如果找到了更短的路径，我们就做两件事：

    • 更新 dist[nextNode] 为这个新的、更小的值。
    • 将这个新的距离和节点 (newTime, nextNode) 加入到优先队列中。注意，同一个节点可能会被多次加入队列（带着不同的距离），但当我们从队列中取出它时，只有最小的那个距离是有效的，更大的距离会被直接忽略。

让我们用上面的例子走一遍流程：

  • 初始状态:

    • dist = [Inf, 0, Inf, Inf, Inf]
    • minHeap = [(0, 2)]

  • 第一轮循环:

    • 弹出堆顶：currentNode=2, currentTime=0。
    • 遍历节点2的邻居：(1, 1) 和 (3, 1)。
    • 对于邻居1：新距离 = 0 + 1 = 1。这个值 1 < dist[1] (Inf)，所以更新 dist[1] = 1，并将 (1, 1) 加入堆。
    • 对于邻居3：新距离 = 0 + 1 = 1。这个值 1 < dist[3] (Inf)，所以更新 dist[3] = 1，并将 (1, 3) 加入堆。
    • 现在：dist = [Inf, 1, 0, 1, Inf]，minHeap = [(1, 1), (1, 3)]。

  • 第二轮循环:

    • 弹出堆顶，假设弹出 (1, 1)（弹出 (1, 3) 也可以，顺序不影响最终结果）。
    • currentNode=1, currentTime=1。
    • 节点1没有出边，无事可做。
    • 现在：dist 不变，minHeap = [(1, 3)]。

  • 第三轮循环:

    • 弹出堆顶：currentNode=3, currentTime=1。
    • 遍历节点3的邻居：(4, 1)。
    • 对于邻居4：新距离 = 1 + 1 = 2。这个值 2 < dist[4] (Inf)，所以更新 dist[4] = 2，并将 (2, 4) 加入堆。
    • 现在：dist = [Inf, 1, 0, 1, 2]，minHeap = [(2, 4)]。

  • 第四轮循环:

    • 弹出堆顶：currentNode=4, currentTime=2。
    • 节点4没有出边，无事可做。
    • 现在：minHeap 为空，循环结束。

步骤四：得到答案
算法结束后，dist 数组中存储的就是从起点 k 到每个节点的最短时间。

  • 我们检查 dist 数组（从索引1到n）：
    • 如果其中还存在 Infinity（初始时设置的最大值），说明有节点无法从 k 到达，根据题意返回 -1。
    • 如果所有节点都有有限的距离值，那么答案就是所有这些距离中的最大值，因为它代表了信号传到最后那个节点所需的时间。

接上例，dist[1...4] = [1, 0, 1, 2]。所有节点都可达，最大值是2。所以答案是2。

总结
解决这个问题的清晰步骤是：

  1. 建图：使用邻接表表示网络结构。
  2. 初始化：创建距离数组dist（起点为0，其余为无穷大）和最小堆minHeap（初始放入起点(0, k)）。
  3. Dijkstra循环：当堆不为空时，弹出当前最近节点，遍历其邻居，如果找到更短路径则更新dist并将新距离加入堆。
  4. 计算答案：检查dist数组，若有不可达节点返回-1，否则返回数组中的最大值。

这个算法的时间复杂度主要取决于优先队列的操作，通常是 O(E log V)，其中 E 是边的数量，V 是节点的数量，非常高效。

LeetCode 743. 网络延迟时间 题目描述 有 n 个网络节点，标记为从 1 到 n 。同时给你一个列表 times ，列表中的每个元素是一个三元组 (u, v, w) ，表示一条有向边。其中 u 是源节点， v 是目标节点， w 是一个信号从源节点传输到目标节点需要的时间。 现在，我们从某个给定的节点 k 发出一个信号。需要多久才能使所有节点都收到信号？如果无法使所有节点都收到信号，则返回 -1 。 解题过程 这个问题的核心是：给定一个带权有向图和一个起点，我们需要找出从起点到所有其他节点的最短距离，然后取这些最短距离中的最大值。这个最大值就是信号传遍整个网络所需的最短时间。如果存在无法到达的节点，我们就返回 -1。这正是一个典型的 单源最短路径 问题。由于边的权重（时间）都是正数，我们可以使用著名的 Dijkstra 算法 。 Dijkstra 算法的核心思想是 贪心 和 广度优先搜索（BFS）的扩展 。它每次都从"尚未确定最短路径的节点"中，选择一个距离起点最近的节点，然后通过这个节点来更新其邻居节点的距离。 让我们一步步来： 步骤一：构建图（邻接表） 我们首先需要将输入的 times 列表转换成一种方便我们快速查询的数据结构，最常用的是 邻接表 。 我们可以使用一个字典（Map）或者一个列表的列表（List of Lists）。这里我们使用列表的列表，索引代表节点编号（注意题目节点从1开始，我们的索引0不用或对应节点1）。 graph[i] 存储的是从节点 i 可以直接到达的邻居节点以及所需的时间。具体来说， graph[i] 是一个由 (邻居节点, 时间) 组成的列表。 例子 ：假设 n=4, times = [ [ 2,1,1], [ 2,3,1], [ 3,4,1] ], k=2 我们构建的邻接表 graph 如下（索引0我们不用，从索引1开始）： graph[1] : [ ] (节点1没有出边) graph[2] : [ (1, 1), (3, 1) ] (从2可以到1，时间1；从2可以到3，时间1) graph[3] : [ (4, 1) ] (从3可以到4，时间1) graph[4] : [ ] (节点4没有出边) 步骤二：初始化数据结构 我们需要两个关键的数据结构： 距离数组（ dist ） ： dist[i] 表示从起点 k 到节点 i 的 当前已知的最短距离 。初始时，我们将起点 k 到自己的距离设为 0 ( dist[k] = 0 )，因为自己到自己不需要时间。对于其他所有节点，因为一开始我们不知道距离是多少，所以先设为一个非常大的数（比如 Infinity 或 Integer.MAX_VALUE ），表示"尚未到达"。 优先队列（最小堆， minHeap ） ：这个队列帮助我们快速找到"当前距离起点最近的未处理节点"。队列中的每个元素是 (从起点到该节点的当前最短距离, 节点编号) 。我们总是从堆顶取出距离最小的节点进行处理。 接上例，起点 k=2。 初始化 dist 数组： dist = [Inf, 0, Inf, Inf, Inf] (索引0无用，dist[ 1]对应节点1，dist[ 2 ]对应节点2（起点）...) 初始化 minHeap ：首先将起点 (0, 2) 加入堆中。 步骤三：执行 Dijkstra 算法 这是一个循环过程，只要优先队列不为空，我们就继续： 取出当前最近节点 ：从最小堆中弹出堆顶元素，我们得到 (currentTime, currentNode) ，其中 currentTime 就是从起点 k 到 currentNode 的 最终确定的最短距离 。为什么是最终确定的？因为我们是基于贪心策略，所有比它短的路径都已经被处理过了，所以当前这个值不可能再被更小的值更新。 遍历邻居节点 ：查看当前节点 currentNode 的所有邻居。对于每一个邻居节点 nextNode 和它们之间的边权重（时间） time ，我们进行以下计算： 新的潜在距离 = currentTime + time 如果这个 新的潜在距离 小于我们之前记录的到 nextNode 的距离 dist[nextNode] ，说明我们找到了一条更短的路径。 更新距离和堆 ：如果找到了更短的路径，我们就做两件事： 更新 dist[nextNode] 为这个新的、更小的值。 将这个新的距离和节点 (newTime, nextNode) 加入到优先队列中。注意，同一个节点可能会被多次加入队列（带着不同的距离），但当我们从队列中取出它时，只有最小的那个距离是有效的，更大的距离会被直接忽略。 让我们用上面的例子走一遍流程： 初始状态 : dist = [Inf, 0, Inf, Inf, Inf] minHeap = [(0, 2)] 第一轮循环 : 弹出堆顶： currentNode=2 , currentTime=0 。 遍历节点2的邻居： (1, 1) 和 (3, 1) 。 对于邻居1：新距离 = 0 + 1 = 1。这个值 1 < dist[1] (Inf)，所以更新 dist[1] = 1 ，并将 (1, 1) 加入堆。 对于邻居3：新距离 = 0 + 1 = 1。这个值 1 < dist[3] (Inf)，所以更新 dist[3] = 1 ，并将 (1, 3) 加入堆。 现在： dist = [Inf, 1, 0, 1, Inf] ， minHeap = [(1, 1), (1, 3)] 。 第二轮循环 : 弹出堆顶，假设弹出 (1, 1) （弹出 (1, 3) 也可以，顺序不影响最终结果）。 currentNode=1 , currentTime=1 。 节点1没有出边，无事可做。 现在： dist 不变， minHeap = [(1, 3)] 。 第三轮循环 : 弹出堆顶： currentNode=3 , currentTime=1 。 遍历节点3的邻居： (4, 1) 。 对于邻居4：新距离 = 1 + 1 = 2。这个值 2 < dist[4] (Inf)，所以更新 dist[4] = 2 ，并将 (2, 4) 加入堆。 现在： dist = [Inf, 1, 0, 1, 2] ， minHeap = [(2, 4)] 。 第四轮循环 : 弹出堆顶： currentNode=4 , currentTime=2 。 节点4没有出边，无事可做。 现在： minHeap 为空，循环结束。 步骤四：得到答案 算法结束后， dist 数组中存储的就是从起点 k 到每个节点的最短时间。 我们检查 dist 数组（从索引1到n）： 如果其中还存在 Infinity （初始时设置的最大值），说明有节点无法从 k 到达，根据题意返回 -1 。 如果所有节点都有有限的距离值，那么答案就是所有这些距离中的 最大值 ，因为它代表了信号传到最后那个节点所需的时间。 接上例， dist[1...4] = [1, 0, 1, 2] 。所有节点都可达，最大值是2。所以答案是2。 总结 解决这个问题的清晰步骤是： 建图 ：使用邻接表表示网络结构。 初始化 ：创建距离数组 dist （起点为0，其余为无穷大）和最小堆 minHeap （初始放入起点(0, k)）。 Dijkstra循环 ：当堆不为空时，弹出当前最近节点，遍历其邻居，如果找到更短路径则更新 dist 并将新距离加入堆。 计算答案 ：检查 dist 数组，若有不可达节点返回-1，否则返回数组中的最大值。 这个算法的时间复杂度主要取决于优先队列的操作，通常是 O(E log V)，其中 E 是边的数量，V 是节点的数量，非常高效。