LeetCode 743. 网络延迟时间

字数 2398 2025-10-28 00:29:09

LeetCode 743. 网络延迟时间

题目描述：
有 n 个网络节点，标记为从 1 到 n。我们会给你一个列表 times，表示信号经过有向边的传递时间。times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点，wi 是一个信号从源节点传递到目标节点需要的时间。现在，我们从某个节点 k 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点都收到信号，则返回 -1。

解题过程：
这个问题可以抽象为：在一个有向加权图中，给定一个起点 k，我们需要找出从 k 到所有其他节点的最短路径。那么，所有节点都收到信号的时间，实际上就是所有最短路径中的最大值（因为我们要等最慢的那个节点收到信号）。如果存在无法到达的节点，我们就返回 -1。这是一个典型的单源最短路径问题。由于边的权重（时间）都是正数，我们可以使用著名的 Dijkstra 算法。

Dijkstra 算法的核心思想是广度优先搜索与贪心策略的结合。它每次都从"未确定最短路径的节点集合"中，选择一个当前距离起点最近的节点，然后通过这个节点来更新其邻居节点到起点的距离。

让我们一步步来：

构建图：
首先，我们需要一种数据结构来存储这个图，这样给定一个节点，我们能快速找到它的所有邻居以及到这些邻居的边的权重。通常我们使用"邻接表"来实现。例如，对于一个节点 u，我们存储一个列表，列表中的每个元素是 (v, w)，表示有一条从 u 到 v 的边，权重为 w。
初始化距离数组：
我们需要一个数组 dist，dist[i] 表示从起点 k 到节点 i 的当前已知最短距离。在算法开始时，我们只知道起点到自己的距离是 0，所以我们将 dist[k] 初始化为 0。对于其他所有节点，因为我们还不知道距离，所以先初始化为一个"无穷大"的值（在代码中可以用一个非常大的数，比如 float('inf') 来表示）。
初始化优先队列（最小堆）：
为了高效地找到当前距离起点最近的未处理节点，我们使用一个优先队列（通常用最小堆实现）。这个队列的元素是 (当前已知距离, 节点)。一开始，我们把起点 (0, k) 放入队列。
主循环：
只要队列不为空，我们就重复以下步骤：
a. 出队： 从优先队列中弹出当前距离最小的节点，我们称这个节点为 current_node，它到起点的当前距离是 current_distance。
b. 检查是否已确定： 由于贪心策略，一旦一个节点被从队列中弹出（基于当前最小的距离），这个距离就是它的最终最短距离，不会再被更新得更小。但是，在算法运行过程中，同一个节点可能会因为被多次更新而多次入队。因此，当我们弹出 (current_distance, current_node) 时，需要检查一下：如果 current_distance 大于我们 dist 数组中记录的 current_node 的最短距离 dist[current_node]，说明这个节点之前已经被处理过了（用一个更小的距离），当前这次出队是一个过时的、无效的结果，我们直接忽略它，继续处理队列中的下一个节点。
c. 处理邻居： 如果 current_distance 等于 dist[current_node]（说明这是最新、最小的距离），那么我们就来"松弛"这个节点的所有邻居。对于 current_node 的每一个邻居节点 neighbor 以及连接它们的边的权重 weight，我们计算一条新的路径距离：new_distance = current_distance + weight。
d. 更新距离： 如果计算出的 new_distance 小于 dist 数组中记录的 neighbor 节点的当前最短距离 dist[neighbor]，那么我们就找到了一个更短的路径。于是，我们更新 dist[neighbor] 为 new_distance，并将这个新的距离和节点 (new_distance, neighbor) 加入到优先队列中，以便后续处理。
得到结果：
当队列为空时，意味着我们已经处理完了所有从起点 k 可以到达的节点。此时，dist 数组中存储的就是从 k 到每个节点的最短路径长度。我们遍历整个 dist 数组（注意节点编号从1到n，索引0我们不用）：
- 如果任何一个距离的值仍然是初始的"无穷大"，说明这个节点从 k 出发无法到达，根据题目要求，我们返回 -1。
- 如果所有节点都是有限的距离，那么我们就找出 dist 数组中的最大值，这个最大值就是信号传遍整个网络所需的时间。

总结步骤：

用邻接表构建图。
初始化距离数组 dist，除起点外全为无穷大，起点为0。
初始化最小堆（优先队列），放入起点 (0, k)。
当堆不为空：
a. 弹出堆顶 (d, node)。
b. 如果 d > dist[node]，跳过。
c. 否则，遍历 node 的邻居 n 和权重 w：
- 计算新距离 nd = d + w。
- 如果 nd < dist[n]，则更新 dist[n] = nd，并将 (nd, n) 入堆。
遍历 dist 数组（从1到n）：
- 若有值为无穷大，返回 -1。
- 否则，返回数组中的最大值。

这个算法高效地找到了单源最短路径，其时间复杂度取决于优先队列的实现，使用二叉堆时约为 O(E log V)，其中 E 是边数，V 是节点数。

LeetCode 743. 网络延迟时间题目描述：有 n 个网络节点，标记为从 1 到 n 。我们会给你一个列表 times ，表示信号经过有向边的传递时间。 times[i] = (ui, vi, wi) ，其中 ui 是源节点， vi 是目标节点， wi 是一个信号从源节点传递到目标节点需要的时间。现在，我们从某个节点 k 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点都收到信号，则返回 -1 。解题过程：这个问题可以抽象为：在一个有向加权图中，给定一个起点 k ，我们需要找出从 k 到所有其他节点的最短路径。那么，所有节点都收到信号的时间，实际上就是所有最短路径中的最大值（因为我们要等最慢的那个节点收到信号）。如果存在无法到达的节点，我们就返回 -1 。这是一个典型的单源最短路径问题。由于边的权重（时间）都是正数，我们可以使用著名的 Dijkstra 算法。 Dijkstra 算法的核心思想是广度优先搜索与贪心策略的结合。它每次都从"未确定最短路径的节点集合"中，选择一个当前距离起点最近的节点，然后通过这个节点来更新其邻居节点到起点的距离。让我们一步步来：构建图：首先，我们需要一种数据结构来存储这个图，这样给定一个节点，我们能快速找到它的所有邻居以及到这些邻居的边的权重。通常我们使用"邻接表"来实现。例如，对于一个节点 u ，我们存储一个列表，列表中的每个元素是 (v, w) ，表示有一条从 u 到 v 的边，权重为 w 。初始化距离数组：我们需要一个数组 dist ， dist[i] 表示从起点 k 到节点 i 的当前已知最短距离。在算法开始时，我们只知道起点到自己的距离是 0 ，所以我们将 dist[k] 初始化为 0 。对于其他所有节点，因为我们还不知道距离，所以先初始化为一个"无穷大"的值（在代码中可以用一个非常大的数，比如 float('inf') 来表示）。初始化优先队列（最小堆）：为了高效地找到当前距离起点最近的未处理节点，我们使用一个优先队列（通常用最小堆实现）。这个队列的元素是 (当前已知距离, 节点) 。一开始，我们把起点 (0, k) 放入队列。主循环：只要队列不为空，我们就重复以下步骤： a. 出队：从优先队列中弹出当前距离最小的节点，我们称这个节点为 current_node ，它到起点的当前距离是 current_distance 。 b. 检查是否已确定：由于贪心策略，一旦一个节点被从队列中弹出（基于当前最小的距离），这个距离就是它的最终最短距离，不会再被更新得更小。但是，在算法运行过程中，同一个节点可能会因为被多次更新而多次入队。因此，当我们弹出 (current_distance, current_node) 时，需要检查一下：如果 current_distance 大于我们 dist 数组中记录的 current_node 的最短距离 dist[current_node] ，说明这个节点之前已经被处理过了（用一个更小的距离），当前这次出队是一个过时的、无效的结果，我们直接忽略它，继续处理队列中的下一个节点。 c. 处理邻居：如果 current_distance 等于 dist[current_node] （说明这是最新、最小的距离），那么我们就来"松弛"这个节点的所有邻居。对于 current_node 的每一个邻居节点 neighbor 以及连接它们的边的权重 weight ，我们计算一条新的路径距离： new_distance = current_distance + weight 。 d. 更新距离：如果计算出的 new_distance 小于 dist 数组中记录的 neighbor 节点的当前最短距离 dist[neighbor] ，那么我们就找到了一个更短的路径。于是，我们更新 dist[neighbor] 为 new_distance ，并将这个新的距离和节点 (new_distance, neighbor) 加入到优先队列中，以便后续处理。得到结果：当队列为空时，意味着我们已经处理完了所有从起点 k 可以到达的节点。此时， dist 数组中存储的就是从 k 到每个节点的最短路径长度。我们遍历整个 dist 数组（注意节点编号从1到n，索引0我们不用）：如果任何一个距离的值仍然是初始的"无穷大"，说明这个节点从 k 出发无法到达，根据题目要求，我们返回 -1 。如果所有节点都是有限的距离，那么我们就找出 dist 数组中的最大值，这个最大值就是信号传遍整个网络所需的时间。总结步骤：用邻接表构建图。初始化距离数组 dist ，除起点外全为无穷大，起点为0。初始化最小堆（优先队列），放入起点 (0, k) 。当堆不为空： a. 弹出堆顶 (d, node) 。 b. 如果 d > dist[node] ，跳过。 c. 否则，遍历 node 的邻居 n 和权重 w ： - 计算新距离 nd = d + w 。 - 如果 nd < dist[n] ，则更新 dist[n] = nd ，并将 (nd, n) 入堆。遍历 dist 数组（从1到n）：若有值为无穷大，返回 -1 。否则，返回数组中的最大值。这个算法高效地找到了单源最短路径，其时间复杂度取决于优先队列的实现，使用二叉堆时约为 O(E log V)，其中 E 是边数，V 是节点数。