다익스트라

다익스트라 알고리즘은 source node로 부터 모든 node까지의 최단거리를 구하는 알고리즘이다.

다익스트라 알고리즘을 알기 위해서는

먼저 heapq부터 알고 해야 한다.

그전에 heapq의 특징을 알고가면 좋다.

[heapq]

• 완전 이진 트리 형태
• 부모 노드 키값이 자식 노드 키값보다 항상 작다(최소힙)
• 키값의 대소관계는 부모/자식 관계에서만 성립하고, 자식끼리의 대소관계는 없다

다익스트라 알고리즘

1. node가 숫자일때

1916번: 최소비용 구하기

import heapq
import sys

input = sys.stdin.readline
N = int(input())
M = int(input())
graph = [[] for _ in range(N+1)]
visit = [1e9]*(N+1)

for i in range(M):
    a,b,c = map(int,input().split())
    graph[a].append((c,b))

start,end = map(int, input().split())

def sol(start):
    global graph,visit
    pq = []
    heapq.heappush(pq, (0,start))
    visit[start] = 0

    while pq:
        c_dist,cur = heapq.heappop(pq)

        if visit[cur] < c_dist : continue

        for n_dist,next in graph[cur]:
            weight = n_dist + c_dist
            if visit[next] > weight:
                visit[next] = weight
                heapq.heappush(pq, (weight,next))

sol(start)
print(visit[end])