[알고리즘] 다익스트라

❓ 다익스트라 알고리즘을 언제 사용할까

최단 경로 구하기

❓ 다익스트라 알고리즘 풀이방법 정리

1️⃣ 우선순위 큐 구현을 위해 heapq 가져오기

import sys
import heapq

2️⃣ 빠른 입력받기와 최대값 저장을 위해 sys 가져오기

input = sys.stdin.readline
INF = sys.maxsize

3️⃣ 그래프 배열 선언, 입력받기

graph[현재노드] = (거리, 다음노드)

graph = [[] for _ in range(n+1)]
for i in range(e):
    a, b, w = map(int, input().split())
    graph[a].append((w, b))
    graph[b].append((w, a))

4️⃣ 최소 거리 값을 저장하는 memo 배열 선언, heap 배열 선언

def dij(start, end):
    memo = [INF] * (n + 1)
    heap = []

5️⃣ 시작점에서의 memo 배열 저장 & heap에 (0, start) 즉 시작노드 넣기

    memo[start] = 0
    heapq.heappush(heap, (0, start))

6️⃣ heap 배열이 비지 않는 동안 배열에서 (예전거리, 현재노드) 노드 하나씩 꺼내서 각각 저장하기

    while heap:
        prev_weigh, cur_node = heapq.heappop(heap)

7️⃣ 만약 저장되어 있는 memo 배열 현재 노드의 거리가 예전 거리보다 짧다면 밑에 건너뛰기 continue

        if memo[cur_node] < prev_weigh:
            continue

8️⃣ 현재 노드와 연결되어 있는 노드들 순회
(현재거리, 다음노드)
다음거리 = 이전거리 + 현재거리

        for cur_weigh, next_node in graph[cur_node]:
            next_weigh = prev_weigh + cur_weigh

9️⃣ 만약 저장되어 있는 memo 배열 다음 노드의 거리가 다음거리보다 길다면 거리 갱신
memo[다음노드] = 다음거리
heap 배열에 (다음노드, 다음거리) push

            if next_weigh < memo[next_node]:
                memo[next_node] = next_weigh
                heapq.heappush(heap, (next_node, next_weigh))

    return memo[end]