[Algorithm] Dijkstra

예시

초기화

노드: (다른 노드, 거리)
1: (2, 7), (3, 9), (6, 14)
2: (1, 7), (3, 10), (4, 15)
3: (1, 9), (2, 10), (4, 11), (6, 2)
4: (2, 15), (3, 11), (5, 6)
5: (4, 6), (6, 9)
6: (1, 14), (3, 2), (5, 9)

Step by Step

편의상 distance 배열의 index는 1부터 시작한다고 하자.
Q는 Min Heap Priority Queue로, (cost, node)와 같이 저장한다.

초기상태

Q = [(0, 1)]
S = {}
distance = [0, inf, inf, inf, inf]

1단계: 노드 1 방문

Q = [(0, 1)]
S = {}

pop Q & add to S
S = {1}

인접 노드들 처리

• 2번: distance[2] = inf > 7 → 업데이트 및 push
• 3번: distance[3] = inf > 9 → 업데이트 및 push
• 6번: distance[6] = inf > 14 → 업데이트 및 push

Q = [(7, 2), (9, 3), (14, 6)]
distance = [0, 7, 9, inf, inf, 14]

2단계: 노드 2 방문

Q = [(7, 2), (9, 3), (14, 6)]
S = {1}

pop Q & add to S
S = {1, 2}

인접 노드들 처리

• 1번: 무시
• 3번: distance[3] = 9 < 7 + 10 → 무시
• 4번: distance[4] = inf < 7 + 15 = 22 → 업데이트 및 push

Q = [(9, 3), (14, 6), (22, 4)]
distance = [0, 7, 9, 22, inf, 14]

3단계: 노드 3 방문

Q = [(9, 3), (14, 6), (22, 4)]
S = {1, 2}

pop Q & add to S
S = {1, 2, 3}

인접 노드들 처리

• 1번: 무시
• 2번: 무시
• 4번: distance[4] = 22 > 9 + 11 = 20 → 업데이트 및 push
• 6번: distance[6] = 14 > 9 + 2 = 11 → 업데이트 및 push

Q = [(11, 6), (14, 6), (22, 4), (20, 4)]
distance = [0, 7, 9, 20, inf, 11]

4단계: 노드 6 방문

Q = [(11, 6), (14, 6), (22, 4), (20, 4)]
S = {1, 2, 3}

pop Q & add to S
S = {1, 2, 3, 6}

인접 노드들 처리

• 1번: 무시
• 3번: 무시
• 5번: distance[5] = inf > 11 + 9 = 20 → 업데이트 및 push

Q = [(14, 6), (20, 4), (22, 4), (20, 5)]
distance = [0, 7, 9, 20, 20, 11]

5단계: 노드 6 다시 등장 (중복)

Q = [(14, 6), (20, 4), (22, 4), (20, 5)]
S = {1, 2, 3, 6}

pop Q & add to S → 이미 S에 존재하므로 무시

Q = [(20, 4), (20, 5), (22, 4)]

6단계: 노드 4 방문

Q = [(20, 4), (20, 5), (22, 4)]
S = {1, 2, 3, 6}

pop Q & add to S
S = {1, 2, 3, 4, 6}

인접 노드들 처리

• 2번: 무시
• 3번: 무시
• 5번: distance[5] = 20 ≤ 20 + 6 = 26 → 무시

Q = [(20, 5), (22, 4)]
distance = [0, 7, 9, 20, 20, 11]

7단계: 노드 5 방문

Q = [(20, 5), (22, 4)]
S = {1, 2, 3, 4, 6}

pop Q & add to S
S = {1, 2, 3, 4, 5, 6}

인접 노드들 처리

• 4번: 무시
• 6번: 무시

Q = [(22, 4)]

8단계: 노드 4 중복 등장 → 무시

Q = [(22, 4)]
S = {1, 2, 3, 4, 5, 6}

pop Q → 이미 S에 있으므로 무시

단계별 실행 표

단계	방문 노드	Q 상태	S	distance[]
1	1	[]	{1}	[0, 7, 9, inf, inf, 14]
2	2	[(9,3), (14,6), (22,4)]	{1,2}	[0, 7, 9, 22, inf, 14]
3	3	[(11,6), (14,6), (22,4), (20,4)]	{1,2,3}	[0, 7, 9, 20, inf, 11]
4	6	[(14,6), (20,4), (22,4), (20,5)]	{1,2,3,6}	[0, 7, 9, 20, 20, 11]
5	6 (중복)	[(20,4), (20,5), (22,4)]	{1,2,3,6}	[0, 7, 9, 20, 20, 11]
6	4	[(20,5), (22,4)]	{1,2,3,4,6}	[0, 7, 9, 20, 20, 11]
7	5	[(22,4)]	{1,2,3,4,5,6}	[0, 7, 9, 20, 20, 11]
8	4 (중복)	[]	{1,2,3,4,5,6}	[0, 7, 9, 20, 20, 11]

[코드] Dijkstra with Priority Queue

# Dijkstra Algorithm with Adjacent List and Priority Heap
# https://www.acmicpc.net/problem/1753

from math import inf
from heapq import heappush as push, heappop as pop

# 입력
V, E = map(int, input().split())
K = int(input()) - 1 # 시작 정점 번호
EDGES = [tuple(map(int, input().split())) for _ in range(E)]

# Adjacent List
ADJ_EDGES = [[] for _ in range(V)]

for edge in EDGES:
    ADJ_EDGES[edge[0] - 1].append((edge[2], edge[1] - 1))

# Distance
distance = [inf for _ in range(V)]
distance[K] = 0

# Priority Heap: 거리순으로 정렬
pq = []
push(pq, (0, K))

while pq:
    # 노드 방문
    cost, vertex = pop(pq)
    if distance[vertex] < cost:
        continue

    # 가장 작은 weight 가진 곳으로..
    for next_c, next_v in ADJ_EDGES[vertex]:
        cmp_distance = distance[vertex] + next_c
        if cmp_distance < distance[next_v]:
            distance[next_v] = cmp_distance
            push(pq, (cmp_distance, next_v))

print(*map(lambda x: str(x).upper(), distance), sep="\n")