[LEET CODE] 743. Network Delay Time ( 다익스트라 알고리즘)

# Problem

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target. We will send a signal from a given node k. Return the time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1. Constraints: 1 <= k <= n <= 100 1 <= times.length <= 6000 times[i].length == 3 1 <= ui, vi <= n ui != vi 0 <= wi <= 100 All the pairs (ui, vi) are unique. (i.e., no multiple edges.)

 

# My Answer

import collections
import heapq
class Solution:    
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        route = collections.defaultdict(dict)
        for u ,v, w in times:
            route[u][v]=w # (시간, 노드) 저장
        distances = {node: float('inf') for node in range(1,n+1)} # 최단 경로 저장
        distances[k]=0
        queue=[]
        heapq.heappush(queue,[distances[k],k]) # queue에 현재거리, 노드 저장
        
        while queue:
            current_distance, current_node = heapq.heappop(queue)
            if distances[current_node]<current_distance: # 저장된 거리가 현재 거리보다 짧을 경우 skip
                continue
            for v,w in route[current_node].items(): # 현재 거리에 연결된 노드들
                distance = current_distance + w
                if distance<distances[v]: # 저장되어있는 거리보다 현재 거리가 작으면 업데이트
                    distances[v] = distance
                    heapq.heappush(queue,[distance,v])
        
        if max(distances.values())==inf: # 탐색되지 않은 노드가 있다면 -1 리턴
            return -1
        else:
            return max(distances.values()) # 가장 거리가 먼 노드의 거리 반환

다익스트라 알고리즘을 이용해서 첫 정점부터 각 노드까지의 최단 거리를 구한 후 가장 값이 큰 값을 리턴한다

어떤 값이 아직 Inf 인 경우 -> 모든 노드가 탐색되지 않았으므로 -1 리턴

 

# Solution 1 - 다익스트라 알고리즘 구현

import collections
import heapq


class Solution:
    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)]
        dist = collections.defaultdict(int)

        # 우선 순위 큐 최소값 기준으로 정점까지 최단 경로 삽입
        while Q:
            time, node = heapq.heappop(Q) # time 기준 최소값 pop
            if node not in dist:
                dist[node] = time
                for v, w in graph[node]:
                    alt = time + w
                    heapq.heappush(Q, (alt, v))

        # 모든 노드 최단 경로 존재 여부 판별
        if len(dist) == N:
            return max(dist.values())
        return -1

모든 노드를 먼저 dist에 삽입하지 않고 탐색되는 노드만 삽입

dist의 길이로 모든 노드가 탐색되었는지 확인하고 max값 리턴, 아닌 경우 -1 리턴

Q에서 하나씩 pop 할때, 시간 기준 최소값 먼저 -> 이미 dist에 들어있다면 skip하므로 따로 거리 비교 안해줘도 최소 거리 계산 가능

(계속 거리를 더해주므로 나중에 오는 건 더 큼)

---

# 다익스트라 알고리즘 (dijkstra algorithm) 참고

너비 우선 탐색 (BFS) 와 유사

하나의 정점에서 다른 모든 정점 간의 각각 최단거리 구하기

 

1. 초기 정점만 0, 다른 정점들은 inf 로 설정

2. 우선 순위 큐에 초기 정점 삽입

3. 우선순위 큐에서 하나씩 꺼내서

   첫 정점에서 각 노드로 가는 거리가 현재 저장되어 있는 거리보다 짧으면 없데이트하고 우선순위 큐에 각 노드 삽입

4. 우선순위 큐에 꺼낼 노드가 없을 때까지 반복