다익스트라 알고리즘

다익스트라 알고리즘은 방향 그래프 혹은 무방향 그래프에서 하나의 시작점로부터 다른 모든 정점까지의 최단 거리를 구해주는 알고리즘입니다.

플로이드 알고리즘은 모든 정점 쌍 사이의 최단 거리를 구하는 알고리즘인 반면 다익스트라 알고리즘은 하나의 시작점으로부터 다른 모든 정점까지의 최단 거리를 구하는 알고리즘입니다.

구현

우선순위 큐 사용

import heapq
import sys

V, E = map(int, sys.stdin.readline().strip().split())
K = int(input())

graph = dict()

pq = []

for _ in range(E):
    start, end, w = map(int, sys.stdin.readline().strip().split())
    if start not in graph:
        graph[start] = list()
    graph[start].append([start, end, w])

distances = [987654321 for _ in range(V)]
distances[K-1] = 0
   
heapq.heappush(pq, (0,[K,K,0]))

while len(pq) > 0:
    pop_edge = heapq.heappop(pq)[1]
    cur_node = pop_edge[1]
    cur_distance = pop_edge[2]
    
    if cur_distance > distances[cur_node-1]:
        continue
    
    if cur_node in graph:
        for edge in graph[cur_node]:
            new_distance = cur_distance + edge[2]
            if new_distance < distances[edge[1]-1]:
                distances[edge[1]-1] = new_distance
                new_list = [K, edge[1],new_distance]
                heapq.heappush(pq, (new_distance, new_list))
    

for i in distances:
    if i == 987654321:
        print('INF')
    else:
        print(i)