[알고리즘] 네트워크 딜레이 타임

네트워크 딜레이 타임

책 풀이

def networkDelayTime(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)] # 처음 K에서 시작하니 K에서 K까지의 소요시간은 0이다

    dist = collections.defaultdict(int)

    #우선순위 큐 최솟값 기준으로 정점까지 최단 경로 삽입
    while Q:
        time, node = heapq.heappop(Q)
        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

기본적인 다익스트라 알고리즘인, 전체 노드만큼의 길이를 무한대로 초기화 한후, 시작점은 0으로하고 진행하는 알고리즘만 알고 있었는데, 이 알고리즘은 큐를 이용함으로서 성능이 더 낫다. 처음에는 어떻게 graph에 있는 것이 최적의 시간인지를 보장하는지 궁금했는데, 생각해보니 weight가 전부 양수이니, 나중에 발견하는 경로 원래 걸리시는 시간 이상이다.