🗂️ Graph Theory 2: Dijkstra

📚 Dijkstra

다익스트라 최단 경로 문제는 그래프 자료 구조에서 여러 개의 노드가 주어졌을 때, 특정한 노드(시작점)에서 특정한 노드(도착점)까지의 최단 경로를 구해주는 알고리즘을 설계해야 한다. 특히 다익스트라는 음의 간선이 없을 때 정상적으로 동작하며, 유향 & 무향을 가리지 않고 적용할 수 있다. 다익스트라 알고리즘의 동작을 기술하면 아래와 같다.

• 1) 출발 노드 설정
• 2) 최단 거리 테이블 초기화(출발 노드 값은 0)
• 3) 방문하지 않은 노드 중에서 현재 가장 가까운 노드를 선택(최단 거리 노드)
• 4) 선택된 노드로부터 파생되는 다른 경로값 업데이트
• 5) 모든 노드에 대한 계산 끝날 때까지 3~4번 반복

다익스트라 알고리즘을 설계하는 방법은 크게 두가지가 있다. 먼저 3번을 수행하기 위해 1) 최단 거리 테이블을 매번 선형 탐색하는 알고리즘, 2) 선형 탐색 대신에 힙 정렬을 이용해 가장 가까운 노드를 선택하는 방식이 있다. 1번의 경우 O(V^2) 가 되어 입력 노드가 1000개만 넘어가도 시간 초과를 당하기 때문에, 2번의 경우로 소스 코드를 작성하는 게 바람직하다. 코드 예시는 아래와 같다.

""" Dijkstra implementation """

import sys
import heapq
from typing import List

def dijkstra(x: int, distance: List[int]) -> None:
    h = []
    heapq.heappush(h, (distance[x], x))
    while h:
        min_cost, node = heapq.heappop(h)
        # 방문한 노드 처리: cost를 기준으로 다음 노드를 선정, 따라서 cost가 distance[node]보다 크다면 이미 방문 했던 노드로 볼 수 있음
        if min_cost > distance[node]:
            continue
        for i in graph[node]:
            cost = min_cost + i[0]
            if cost < distance[i[1]]:
                distance[i[1]] = cost
                heapq.heappush(h, (cost, i[1]))

V, E = map(int, sys.stdin.readline().split())
src = int(sys.stdin.readline())

# 1) init graph
graph, costs = [[] for _ in range(V+1)], [float('inf')] * (V+1)
costs[src] = 0
for _ in range(E):
    u, v, weight = map(int, sys.stdin.readline().split())
    graph[u].append((weight, v))

dijkstra(src, costs)
for i in range(1, V+1):
    print(costs[i] if costs[i] != float('inf') else 'INF')