[알고리즘] 다익스트라

개요

다익스트라(dijkstra) 알고리즘은 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다(단 음의 가중치가 없어야 한다).

로직

1. 초기화: 출발점으로부터 최단 거리를 저장할 자료구조를 만들고 출발 노드에는 0을, 다른 노드에는 INF를 채워 넣는다. 또한 우선순위 큐에 시작 노드를 삽입한다.
2. 노드 선택: 우선순위 큐에서 거리가 가장 짧은 노드를 선택한다. 선택한 노드의 거리가 이미 저장된 거리보다 크면 무시하고 다음 노드를 선택한다(방문 처리했다는 의미).
3. 인접 노드 업데이트: 현재 선택된 노드와 인접한 노드들의 거리를 확인한다. 현재 노드를 거쳐 인접 노드로 가는 거리가 기존에 알고 있던 거리보다 짧으면, 해당 인접 노드의 거리를 갱신하고, 우선순위 큐에 새로운 거리와 함께 인접 노드를 삽입한다.
4. 반복: 우선순위 큐가 빌 때까지 2 ~ 3 단계를 반복한다. 이렇게하면 시작 노드로부터 모든 노드까지의 최단 거리가 계산된다.

코드 구현

import heapq

def dijkstra(graph, start):
    # 최단 거리를 저장할 자료구조, 기본적으로 INF를 채워넣는다.
    distances = {node: float('inf') for node in graph}
    # 시작노드까지의 거리는 0으로 설정한다.
    distances[start] = 0

    # 방문하지 않은 인접한 노드를 저장할 우선순위 큐를 생성한다.
    pq = []
    # 시작 노드를 넣는다.
    heapq.heappush(pq, (0, start))

    while pq:
        curr_dist, curr_node = heapq.heappop(pq)

        # 기존 거리보다 해당 노드를 거리가 더 길면 다음 인접한 노드를 선택한다.
        if distances[curr_node] < curr_dist:
            continue

        # 인접한 노드를 순회한다.
        for next_node, weight in graph[curr_node]:
            tmp_dist = curr_dist + weight
            # 현재 노드를 거쳐 인접한 노드로 가는 이동거리가 기존 알고 있던 이동거리보다 짧다면 최단 거리를 갱신한다.
            if distances[next_node] > tmp_dist:
                distances[next_node] = tmp_dist
                heapq.heappush(pq, (tmp_dist, next_node))
    return distances

# 그래프 예시
graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('C', 3), ('D', 2)],
    'C': [('D', 5)],
    'D': []
}
# 다익스트라 알고리즘 실행
start_node = 'A'
result = dijkstra(graph, start_node)

print(f"{start_node}부터 다른 노드까지의 최단 거리: {result}")

참조

• Introduction to Algorithms 24.3 다익스트라 알고리즘
• 알고리즘 백과사전: 다익스트라 기법
• 최단 경로(백준 문제)