743. Network Delay Time

최소 비용을 구하는 문제.

음수값이 없어 다익스트라로 해결 가능하다. 

 

 

    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = collections.defaultdict(list)

        for u, v, w in times:
            graph[u].append((v, w))

        distances = {node:float('inf') for node in range(n+1)}
        distances[k] = 0
        q = [(0, k)]

        while q:
            weight, vertex = heapq.heappop(q)

            if weight < distances[vertex]:
                continue

            for new_vertex, new_weight in graph[vertex]:

                distance = weight + new_weight
                if distance < distances[new_vertex]:
                    distances[new_vertex] = distance
                    heapq.heappush(q, (distance, new_vertex))

        distances.pop(0)
        max_value = max(distances.values())

        if max_value == float('inf'):
            return -1
        return max_value

결과값을 구할때 float('inf')를 비교하게 되는데, 이부분을 없앨수 있을까?

 

책 풀이가 좀 더 간결하긴한데, 위에 내 풀이는 다익스트라를 조금만 변형한건데...

다른 풀이를 보면 최단 거리 배열을 무한대로 잡아 놓지 않고, 최단 거리가 들어올때마다 저장을 하고, 

다음에 들어오는 것은 무시한다. 

distances는 항상 최솟값으로 셋팅 되기때문에 무시해도 된다고 책에 써져있다.

    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
      graph = collections.defaultdict(list)

      for u, v, w in times:
          graph[u].append((v, w))
      q = [(0, k)]
      distances = collections.defaultdict(int)

      while q:
          time, node = heapq.heappop(q)

		  # distances에 없을때만 확인한다. 

          if node not in distances:
              distances[node] = time

              for v, w in graph[node]:
                  alt = time + w
                  heapq.heappush(q, (alt, v))

	  # distances길이가 n과 같으면 모두 방문해본것
      if len(distances) == n:
          return max(distances.values())
      return -1