[다익스트라] Network Delay Time

Network Delay Time - LeetCode

import sys
import heapq
 
def networkDelayTime(times, n, k):
    
    def dijkstra(k):
        q = []
        heapq.heappush(q, (0, k))
        distance[k] = 0
        while q:
            dist, node = heapq.heappop(q)
 
            if distance[node] < dist:
                continue
 
            # if visited[node] == 1:
            #     continue
            # visited[node] = 1
 
            for i in graph[node]:
                cost = dist + i[1]
                if cost < distance[i[0]]:
                    distance[i[0]] = cost
                    heapq.heappush(q, (cost, i[0]))
 
    INF = sys.maxsize
    graph = [[] for _ in range(n + 1)]  # 0번 노드는 비워둔다.
    distance = [INF] * (n + 1)
    visited = [0] * (n + 1)
    
    for i in times:
        depart, arrive, cost = i[0], i[1], i[2]
        graph[depart].append((arrive, cost))
        
    dijkstra(k)
    
    for i in range(1, n + 1):
        if distance[i] == INF:
            return -1
    return max(distance[1:])
 
 
times = [[2, 1, 1], [2, 3, 1], [3, 4, 1]]
n = 4
k = 2
print(networkDelayTime(times, n, k))

import heapq
from collections import defaultdict
 
def networkDelayTime(times, n, k):
    graph = defaultdict(list)
    distance = defaultdict(int)
 
    for i in times:
        depart, arrive, cost = i[0], i[1], i[2]
        graph[depart].append((arrive, cost))
 
    q = [(0, k)]
    while q:
        time, node = heapq.heappop(q)
        # node 가 꺼내졌을 때 방문하고 그 순간 최소 거리가 되기 때문에
        # 처음 방문한 경우만 처리한다.
        if node not in distance:
            distance[node] = time
            for v, w in graph[node]:
                alt = time + w
                heapq.heappush(q, (alt, v))
 
    if len(distance) == n:
        return max(distance.values())
    return -1
 
 
times = [[2, 1, 1], [2, 3, 1], [3, 4, 1]]
n = 4
k = 2
print(networkDelayTime(times, n, k))

다익스트라에서 방문한 노드는 최소거리(cost)가 되기 때문에 더이상 방문하지 않아도 된다. 
방문을 나타내는 list인 visited를 만들어서 확인해 볼 수 있다.

다익스트라는 전체적으로 bfs를 구현하는것과 비슷한 것 같다.
bfs는 연결된 모든 노드의 거리가 같기 때문에 큐에 들어온 순서대로 값을 꺼내면 된다. 
하지만 다익스트라에서는 연결된 모든 노드의 거리가 같다는 보장도 없고, 최소 거리를 선택해야 한다. 이 때 최소힙을 사용하여 가장 작은 값을 우선적으로 꺼낸다.