题目

有 N 个网络节点，标记为 1 到 N。

给定一个列表 times，表示信号经过有向边的传递时间。 times[i] = (u, v, w)，其中 u 是源节点，v 是目标节点， w 是一个信号从源节点传递到目标节点的时间。

现在，我们从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1。

示例：
image.png
输入：times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
输出：2

注意：

  1. N 的范围在 [1, 100] 之间。
  2. K 的范围在 [1, N] 之间。
  3. times 的长度在 [1, 6000] 之间。

  4. 所有的边 times[i] = (u, v, w) 都有 1 <= u, v <= N 且 0 <= w <= 100。

    方案一（Dijstra算法）

    1. class Solution:
    2.  def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
    3.      # 问题可以转换为从节点 K 出发，求到最远的一个节点所花费的时间
    4.      # 改为邻接表存储
    5.      # key: 源节点, value: [(传递的时间, 目标节点)]
    6.      adj = {key: [] for key in range(1, N + 1)}
    7.      for time in times:
    8.          adj[time[0]].append((time[2], time[1]))
    10.      # dijkstra 算法，已将时间转换为 负数，方便使用最小堆
    11.      min_distances = [float("inf")] * N  # 第 i 个元素表示从节点 K 到 i 的最短花费时间
    12.      min_distances[K-1] = 0  # 节点到自身花费的时间为 0
    13.      visited = {K, }  # 防止环造成的无限循环
    14.      heap = adj[K][:]
    15.      heapq.heapify(heap)
    16.      while heap:
    17.          total_t, node = heapq.heappop(heap)
    18.          visited.add(node)
    19.          min_distances[node-1] = min(total_t, min_distances[node-1])
    20.          for t, next_node in adj[node]:
    21.              if next_node not in visited:
    22.                  heapq.heappush(heap, (t + total_t, next_node))
    24.      ans = max(min_distances)
    25.      return -1 if ans == float("inf") else ans

    官方实现方式

    1. class Solution(object):
    2.  def networkDelayTime(self, times, N, K):
    3.      graph = collections.defaultdict(list)
    4.      for u, v, w in times:
    5.          graph[u].append((v, w))
    7.      pq = [(0, K)]
    8.      dist = {}
    9.      while pq:
    10.          d, node = heapq.heappop(pq)
    11.          if node in dist: continue
    12.          dist[node] = d
    13.          for nei, d2 in graph[node]:
    14.              if nei not in dist:
    15.                  heapq.heappush(pq, (d+d2, nei))
    17.      return max(dist.values()) if len(dist) == N else -1

    方案二（深度优先搜索）

    ```python class Solution: def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:

    1.  # 深度优先搜索
    2.  graph = collections.defaultdict(list)
    3.  for u, v, w in times:
    4.      graph[u].append((w, v))
    6.  dist = {node: float('inf') for node in range(1, N+1)}  # 最早到达节点的时间
    8.  def dfs(node, total_times):
    9.      # node: 信号到达的节点
    10.      # total_times: 信号到达的时间
    11.      if total_times >= dist[node]:  # 只保留到达该节点最短的时间
    12.          return
    13.      dist[node] = total_times
    14.      for w, v in graph[node]:
    15.          dfs(v, total_times + w)
    17.  dfs(K, 0)
    18.  ans = max(dist.values())
    19.  return ans if ans < float('inf') else -1

```

原文

https://leetcode-cn.com/problems/network-delay-time/
https://leetcode-cn.com/problems/network-delay-time/solution/wang-luo-yan-chi-shi-jian-by-leetcode/