[크래프톤 정글 ] 다익 스트라 알고 리즘

다익스트라 알고리즘이란?

다익스트라 알고리즘(Dijkstra's algorithm)은 그래프에서 단일 출발점에서 모든 다른 노드로의 최단 경로를 찾는 알고리즘이다. 가중치가 있는 그래프에서 가중치가 양수일 때 사용할 수 있으며, 네덜란드의 컴퓨터 과학자 에츠허르 다익스트라(Edsger W. Dijkstra)가 1956년에 고안한 알고리즘이다.

다익스트라 알고리즘의 동작 원리

1. 초기화:
   • 시작 노드를 선택하고, 시작 노드에서 다른 모든 노드까지의 거리를 무한대(∞)로 초기화한다.
   • 시작 노드의 거리는 0으로 설정한다.
   • 아직 방문하지 않은 모든 노드를 포함하는 집합(보통 우선순위 큐를 사용)에 시작 노드를 추가한다.
2. 반복:
   • 큐에서 가장 작은 거리를 가진 노드를 꺼낸다. 이 노드를 현재 노드로 설정한다.
   • 현재 노드의 인접 노드들을 탐색하며, 인접 노드에 도달할 수 있는 경로의 거리를 계산한다.
   • 계산된 새로운 경로의 거리가 현재 알려진 인접 노드까지의 거리보다 짧다면, 인접 노드의 거리를 갱신한다.
   • 갱신된 인접 노드를 큐에 추가한다(이때 큐의 정렬이 다시 이루어진다).
3. 종료:
   • 큐가 비게 되면 알고리즘이 종료되고, 시작 노드에서 다른 모든 노드까지의 최단 경로가 결정된다.

다익스트라 알고리즘의 예시

    A
   / \
  1   4
 /     \
B---2---C
 \     /
  3   1
   \ /
    D

• A에서 출발하여 다른 노드로의 최단 경로를 구하는 과정을 다익스트라 알고리즘으로 계산해보자

초기화

• 각 노드의 초기 거리를 무한대로 설정한다.
  • A: 0 (시작 노드)
  • B: ∞
  • C: ∞
  • D: ∞
• 큐에는 (0, A)가 들어있다.

첫 번째 반복

• 큐에서 (0, A)를 꺼내고, 인접한 노드 B와 C를 탐색한다.
  • A → B: 거리 = 1
    • B의 현재 거리가 무한대이므로 1로 갱신한다.
  • A → C: 거리 = 4
    • C의 현재 거리가 무한대이므로 4로 갱신한다.
• 큐에 (1, B)와 (4, C)를 추가한다.

두 번째 반복

• 큐에서 (1, B)를 꺼내고, 인접한 노드 A, C, D를 탐색한다.
  • B → C: 거리 = 1 + 2 = 3
    • C의 현재 거리가 4이므로 3으로 갱신한다.
  • B → D: 거리 = 1 + 3 = 4
    • D의 현재 거리가 무한대이므로 4로 갱신한다.
• 큐에 (3, C)와 (4, D)를 추가한다.

세 번째 반복

• 큐에서 (3, C)를 꺼내고, 인접한 노드 A, B, D를 탐색한다.
  • C → D: 거리 = 3 + 1 = 4
    • D의 현재 거리가 4로 동일하므로 갱신하지 않는다.
• 큐에는 (4, C)와 (4, D)가 남아있지만, C는 이미 처리되었으므로 넘어간다.

네 번째 반복

• 큐에서 (4, D)를 꺼내고, 인접한 노드 B, C를 탐색한다.
  • 이미 처리된 노드이므로 더 이상 갱신이 없다.

최종 결과

• A에서 출발하는 최단 경로는 다음과 같다.
  • A → B: 1
  • A → C: 3
  • A → D: 4

다익스트라 알고리즘의 시간 복잡도

다익스트라 알고리즘의 시간 복잡도는 그래프의 구현 방법에 따라 달라진다:

• 인접 리스트 + 우선순위 큐(힙): (O((V + E) \log V))
  • 여기서 (V)는 노드의 수, (E)는 간선의 수이다.
  • 우선순위 큐(힙)을 사용하면 노드 간 거리 갱신 및 노드 선택 과정에서의 성능을 높일 수 있다.
• 인접 행렬 + 우선순위 큐(힙): (O(V^2))
  • 노드의 수가 적고 간선의 수가 많은 경우에 유리하다.

다익스트라 알고리즘의 한계

1. 음수 가중치:
   • 다익스트라 알고리즘은 음수 가중치를 가진 그래프에서 올바른 결과를 보장하지 못한다. 음수 가중치가 있는 경우, 벨만-포드 알고리즘과 같은 다른 알고리즘을 사용해야 한다.
2. 모든 쌍 최단 경로 문제:
   • 다익스트라 알고리즘은 단일 출발점에서 모든 다른 노드로의 최단 경로를 찾는 데 유용하지만, 모든 쌍 간의 최단 경로를 찾기 위해서는 플로이드-워셜 알고리즘과 같은 다른 알고리즘이 더 적합하다.

다익스트라 알고리즘의 응용 사례

• 네트워크 라우팅:
  • 다익스트라 알고리즘은 인터넷 프로토콜에서 라우팅 경로를 결정하는 데 널리 사용된다. 예를 들어, OSPF(Open Shortest Path First) 프로토콜이 이를 기반으로 작동한다.
• 지리 정보 시스템(GIS):
  • 지도에서 최단 경로를 찾는 데 사용된다. 예를 들어, GPS 시스템이 사용자 위치에서 목적지까지의 최단 경로를 계산할 때 다익스트라 알고리즘이 활용된다.
• 게임 AI:
  • 게임에서 AI 캐릭터의 경로 찾기 알고리즘으로 사용된다. 캐릭터가 장애물을 피하면서 목적지까지의 최단 경로를 찾을 때 활용된다.

다익스트라 알고리즘의 구현 (Python)

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 neighbor, weight in graph[current_node].items():
            distance = current_distance + weight

            # 새로운 경로가 더 짧은 경우에만 갱신
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

# 예시 그래프
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 노드에서 출발하는 최단 경로 계산
print(dijkstra(graph, 'A'))  # {'A': 0, 'B': 1, 'C': 3, 'D': 4}

요약

다익스트라 알고리즘은 가중치가 양수인 그래프에서 단일 출발점에서 모든 다른 노드로의 최단 경로를 찾는 데 매우 효율적이다. BFS와 유사한 구조를 가지고 있지만, 가중치가 있는 그래프에서 동작하며, 우선순위 큐를 통해 효율성을 높일 수 있다.