IT이야기

다익스트라 알고리즘(Dijkstra's Algorithm): 최단 경로 탐색 알고리즘

Chiba-in 2025. 3. 2. 07:30

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

1. 다익스트라 알고리즘(Dijkstra's Algorithm)의 정의

다익스트라 알고리즘(Dijkstra's Algorithm)은 가중치 그래프에서 특정 출발점에서 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 네트워크 경로 최적화, 내비게이션 시스템, 그래프 기반 문제 해결에 널리 사용됩니다.

✅ 다익스트라 알고리즘의 주요 특징:

  • 가중치가 있는 그래프에서 최단 경로를 찾는 알고리즘
  • 출발 노드에서 모든 노드까지의 최단 경로를 계산
  • 음수 가중치가 없는 그래프에서만 사용 가능
  • 우선순위 큐(힙)를 활용하면 O((V+E) log V)의 효율적인 성능 제공

📌 다익스트라 알고리즘은 최단 경로를 찾는 데 가장 많이 활용되는 알고리즘 중 하나입니다.

🔹 다익스트라 알고리즘의 동작 과정

  1. 출발 노드(시작점)를 설정하고, 해당 노드의 거리를 0으로 설정
  2. 나머지 모든 노드의 거리를 무한대로 설정
  3. 현재 방문하지 않은 노드 중 최단 거리가 가장 작은 노드를 선택
  4. 해당 노드를 방문 처리한 후, 인접한 노드들의 거리를 업데이트
  5. 이 과정을 모든 노드가 방문될 때까지 반복

✔️ 다익스트라 알고리즘 예제 (Python):

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]

    while pq:
        current_distance, current_node = heapq.heappop(pq)
        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(pq, (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}
}
print(dijkstra(graph, 'A'))  # 출력: {'A': 0, 'B': 1, 'C': 3, 'D': 4}

📌 우선순위 큐(힙)를 사용하여 탐색 범위를 줄이면 효율적인 탐색이 가능합니다.

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

구현 방식 시간 복잡도
리스트 사용 O(V²)
우선순위 큐(힙) 사용 O((V+E) log V)

📌 힙을 사용하면 성능이 대폭 개선되어, 대규모 네트워크에서도 효율적으로 동작할 수 있습니다.

🔹 다익스트라 알고리즘의 시각적 표현

✔️ 입력 그래프:

       A
      / \
    (1)  (4)
    /      \
   B --(2)-- C
    \       /
    (5)   (1)
      \   /
        D

✔️ 출발 노드 A에서의 최단 경로 계산:

  1. A → B (1), A → C (4)
  2. B → C (1+2 = 3, 기존 4보다 작으므로 업데이트)
  3. C → D (3+1 = 4, B → D (5)보다 짧음 → 업데이트)
  4. 최단 경로: {'A': 0, 'B': 1, 'C': 3, 'D': 4}

📌 다익스트라 알고리즘은 단계별로 최단 경로를 갱신하면서 최적의 경로를 찾습니다.

🔹 다익스트라 알고리즘의 장점과 단점

✅ 장점:

  • 최단 경로를 정확하게 계산할 수 있음
  • O((V+E) log V)로 비교적 빠른 성능 제공
  • 네트워크 라우팅, 내비게이션 시스템 등에 널리 활용됨

❌ 단점:

  • 음수 가중치가 있는 그래프에서는 사용할 수 없음
  • 경우에 따라 벨만-포드 알고리즘이 필요할 수 있음
  • 우선순위 큐가 없을 경우 O(V²)로 성능이 떨어짐

📌 음수 가중치가 포함된 그래프에서는 벨만-포드 알고리즘을 고려해야 합니다.

🔹 다익스트라 알고리즘 vs 다른 최단 경로 알고리즘 비교

알고리즘 시간 복잡도 음수 가중치 지원 최단 경로 보장
다익스트라 O((V+E) log V) ❌ ✅
벨만-포드 O(VE) ✅ ✅
플로이드-워셜 O(V³) ✅ ✅ (모든 정점 쌍)

📌 다익스트라 알고리즘은 양수 가중치 그래프에서 가장 효율적인 알고리즘 중 하나입니다.

📌 결론

✅ 다익스트라 알고리즘(Dijkstra's Algorithm)은 가중 그래프에서 최단 경로를 찾는 효율적인 알고리즘입니다.
✅ O((V+E) log V)의 성능을 가지며, 우선순위 큐(힙)를 사용하면 매우 빠르게 동작할 수 있습니다.
✅ 네트워크 경로 탐색, 지도 내비게이션, 게임 AI 등 다양한 분야에서 활용됩니다.
✅ 음수 가중치를 포함하는 경우 벨만-포드 알고리즘을 고려해야 합니다.