다익스트라

시작점부터 각 노드들의 최단 거리를 구하는 알고리즘

구현 방법

def dijkstra(start, graph, N):
    INF = float('inf')
    dist = [INF] * (N + 1)
    dist[start] = 0
    pq = [(0, start)]  # (비용, 정점)
 
    while pq:
        cur_cost, cur_node = heapq.heappop(pq)
        
        if cur_cost > dist[cur_node]:  # 이미 처리된 경우 스킵
            continue
        
        for next_cost, next_node in graph[cur_node]:
            new_cost = cur_cost + next_cost
            if new_cost < dist[next_node]:
                dist[next_node] = new_cost
                heapq.heappush(pq, (new_cost, next_node))
    
    return dist