백준 / 1753 / 최단경로 / python

import sys
input = sys.stdin.readline

from heapq import heappop, heappush

v, e = [int(v) for v in input().split()]
start = int(input())

graph = [[] for _ in range(v+1)]

for _ in range(e):
    n, l, w = map(int, input().split())
    graph[n].append((l,w))

dist = [1e9] * (v+1)
dist[start] = 0

h = []
heappush(h, (0, start))

while h:
    dis, node = heappop(h)
    if dist[node] < dis:
        continue
    
    for next_node, next_dis in graph[node]:
        d = dis + next_dis
        if dist[next_node] > d:
            dist[next_node] = d
            heappush(h, (d, next_node))

for i in dist[1:]:
    print(i if i != 1e9 else "INF")

다익스트라 알고리즘

다익스트라 알고리즘은 시작점으로 부터 나머지 정점까지 최단거리를 구할 때 사용하는 알고리즘으로 bfs와 구조는 비슷하지만 일반 리스트가 아닌 heapq를 사용하는 것에 차이가 있다.

heapq에서 정렬되는 기준은 가중치이다.
가중치를 heapq로 사용함으로써 시작 정점에서 가까운 거리부터 탐색하기 때문에 최단거리만 빠르게 파악할 수 있다.