Dijkstra(다익스트라) 알고리즘

Dijkstra 알고리즘은 가중치가 있는 그래프에서 한 시작점에서 다른 모든 정점까지의 최단 경로를 찾는 데 유용하며, GPS, 네트워크 라우팅, 게임 AI 등 다양한 분야에서 널리 사용됩니다.

1. 기본 개념

Dijkstra 알고리즘은 "탐욕적 접근법(Greedy approach)"을 사용하여, 각 단계에서 가장 가까운 정점만 선택하는 방식으로 동작합니다. 이를 통해 시작 노드에서 각 노드까지의 최단 거리를 점진적으로 업데이트해 나갑니다. 중요한 점은 음수 가중치가 없는 그래프에서만 작동한다는 것입니다.

2. 작동 방식

Dijkstra 알고리즘의 작동 방식은 다음과 같은 핵심 절차로 이루어집니다.

• 시작 노드에서 모든 노드까지의 거리를 초기화합니다. 시작 노드는 0, 나머지 노드는 무한대로 설정합니다.
• 우선순위 큐(주로 최소 힙)를 사용하여 방문할 노드를 관리하며, 거리가 짧은 순으로 정렬됩니다.
• 시작 노드에서 출발하여, 인접 노드들로 이동합니다.
• 현재 노드에서 인접 노드까지의 거리를 계산하고, 기존에 저장된 거리보다 짧다면 해당 거리를 업데이트합니다.
• 업데이트된 인접 노드는 우선순위 큐에 추가되어, 큐에서 가장 짧은 거리의 노드를 다시 선택하고 이 과정을 반복합니다.
• 모든 노드를 탐색할 때까지 이 과정을 진행하여, 시작점에서 모든 다른 노드까지의 최단 경로를 찾습니다.

3. 핵심 개념

Dijkstra 알고리즘에 대한 몇가지 중요한 개념을 짚고 넘어가겠습니다!

• 거리 갱신 (Relaxation) : 현재 노드에서 인접 노드로의 경로를 통해 거리를 갱신하는 과정입니다. 시작 노드에서 인접 노드로 가는 최단 거리를 찾기 위해, 기존 거리보다 더 짧은 경로를 발견하면 거리를 업데이트하는 과정이 포함됩니다.
• 우선순위 큐 사용 : Dijkstra 알고리즘은 우선순위 큐(주로 최소 힙)을 사용하여 가장 가까운 노드를 먼저 선택합니다. 이를 통해 필요 없는 노드 탐색을 줄이고 효율적으로 최단 경로를 찾을 수 있습니다.
• 종료 조건 : 더 이상 거리를 갱신할 노드가 없거나, 모든 노드가 방문되었을 때 종료됩니다.

4. 시간 복잡도

• 시간 복잡도는 그래프의 노드 수를 $V$, 간선 수를 $E$라 할 때, 우선순위 큐를 사용하여 $O((V+E)log V$의 시간 복잡도를 갖습니다. 우선순위 큐에서 노드를 꺼내고 삽입하는 시간적 비용을 고려하기 때문입니다.
• Dijkstra 알고리즘은 가중치가 양수일 때 최적의 성능을 발휘하므로, 네트워크 라우팅이나 길찾기와 같은 응용에 적합합니다.

5. 작동 예시

간단한 예시를 들어보겠습니다.

(1) 그래프 예시

    2
A ------- B
|         |
4         1
|         |
C ------- D
    3

• 노드 : A, B, C, D
• 간선 가중치
  • A - B = 2
  • A - C = 4
  • B - D = 1
  • C - D = 3

(2) A에서 모든 노드로 최단 거리 찾기

1. A에서 시작 (거리 = 0)
2. A에서 B로 이동 (거리 = 2), C로 이동 (거리 = 4)
3. B에서 D로 이동 (누적 거리 = 2 + 1 = 3)
4. C에서 D로의 경로 (거리 = 4 + 3 = 7) 는 이미 D까지의 최소 거리(3)보다 크므로 무시

결과적으로, A에서 각 노드까지의 최단 거리는

A -> A = 0
A -> B = 2
A -> C = 4
A -> D = 3

이 됩니다.

이와 같은 과정을 통해, Dijkstra 알고리즘은 점진적으로 노드의 최단 거리를 업데이트해가며 탐색을 진행한다는 기본 개념을 알 수 있습니다.

6. Python으로 구현

(1) 그래프 표현하기

Dijkstra는 가중치가 있는 그래프에서 최단 경로를 찾는 방식이라는 것을 이해했다면, Python에서 이를 구현하기 위해서는 그래프를 인접 리스트로 표현해야합니다. 각 노드에서 연결된 노드와 가중치를 저장하는 딕셔너리를 사용할 수 있습니다.

(2) 우선순위 큐 설정하기

최단 거리를 찾기 위해, Python의 heapq 라이브러리를 이용해 우선순위 큐를 구현할 수 있습니다.

(3) Dijkstra 알고리즘 구현하기

시작 노드에서 모든 다른 노드까지의 최소 거리를 업데이트하며 큐에 노드를 추가합니다.

import heapq

def dijkstra(graph, start):
    # 각 노드까지의 최단 거리 저장할 딕셔너리 (초기값: 무한대)
    distances = {node: float('inf') for node in graph}
    distances[start] = 0  # 시작 노드의 거리는 0으로 설정

    # 우선순위 큐 초기화 및 시작 노드 추가
    priority_queue = [(0, start)]  # (거리, 노드)

    while priority_queue:
        # 현재 거리와 노드를 가져옴
        current_distance, current_node = heapq.heappop(priority_queue)

        # 이미 처리된 노드라면 건너뜀
        if current_distance > distances[current_node]:
            continue

        # 인접한 노드와 가중치를 확인
        for adjacent, weight in graph[current_node]:
            distance = current_distance + weight

            # 최단 거리를 갱신할 수 있는 경우
            if distance < distances[adjacent]:
                distances[adjacent] = distance
                heapq.heappush(priority_queue, (distance, adjacent))

    return distances

• distances 딕셔너리 : 각 노드까지의 최단 거리를 저장합니다.
• priority_queue : 시작 노드로부터 탐색을 시작하여, 거리가 짧은 노드부터 순서대로 탐색합니다.
• while 루프 : 큐에서 노드를 꺼내고, 연결된 노드들로 거리를 업데이트합니다.
• if distance < distances[adjacent] 조건문 : 이미 계산된 거리보다 짧은 거리가 발견되면 업데이트합니다.

(4) 코드 실행

# 그래프 정의 (인접 리스트 형태)
graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('A', 1), ('C', 2), ('D', 5)],
    'C': [('A', 4), ('B', 2), ('D', 1)],
    'D': [('B', 5), ('C', 1)]
}

# A 노드에서 다른 모든 노드까지의 최단 거리 계산
start_node = 'A'
distances = dijkstra(graph, start_node)

print("최단 거리:", distances)

실행 결과

최단 거리: {'A': 0, 'B': 1, 'C': 3, 'D': 4}