发表于 2024.04.28

• 本质就是求单源最短路径，然后返回节点K到其他节点的路径中的最大者即可。

  普通的Dijkstra算法：

  from collections import deque
  
  
  class Solution:
      def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
          adj_list = [[] for _ in range(n + 1)]
          for u, v, w in times:
              adj_list[u].append((v, w))
  
          ans = 0
          dis = [-1] * (n + 1)
          dis[k] = 0
          visited = [False] * (n + 1)
          while True:
              min_u = -1
              min_dis = -1
              for u in range(1, n + 1):
                  if not visited[u] and dis[u] != -1 and (min_dis == -1 or dis[u] < min_dis):
                      min_u = u
                      min_dis = dis[u]
  
              if min_u == -1:
                  break
              visited[min_u] = True
              ans = max(ans, min_dis)
              # relax
              for v, w in adj_list[min_u]:
                  if dis[v] == -1 or dis[v] > dis[min_u] + w:
                      dis[v] = dis[min_u] + w
          if not all(visited[u] for u in range(1, n + 1)):
              return -1
          return ans

  使用堆优化的Dijkstra算法,，但实际表现不如上一个：

  import heapq
  from collections import deque
  
  
  class Solution:
      def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
          adj_list = [[] for _ in range(n + 1)]
          for u, v, w in times:
              adj_list[u].append((v, w))
  
          ans = 0
          dis = [-1] * (n + 1)
          dis[k] = 0
          visited = [False] * (n + 1)
          pq = []
          pq.append((0, k))
          while pq:
              min_dis, min_u = heapq.heappop(pq)
  
              if visited[min_u]:
                  continue
              visited[min_u] = True
              ans = max(ans, min_dis)
              # relax
              for v, w in adj_list[min_u]:
                  if dis[v] == -1 or dis[v] > dis[min_u] + w:
                      dis[v] = dis[min_u] + w
                      heapq.heappush(pq, (dis[v], v))
          if not all(visited[u] for u in range(1, n + 1)):
              return -1
          return ans

• LC 题目链接