Dijkstra 알고리즘 설명

Dijkstra 알고리즘은 가중치가 있는 그래프(모든 가중치가 0 이상)에서 출발 노드로부터 다른 모든 노드까지의 최단 경로를 찾는 알고리즘입니다. 1956년 네덜란드의 컴퓨터 과학자 Edsger W. Dijkstra가 고안하였으며, 오늘날까지도 다양한 분야에서 널리 활용되고 있는 대표적인 그래프 탐색 알고리즘입니다.

이 알고리즘은 최단 경로 문제 중에서도 단일 출발점 최단 경로 문제 (Single-Source Shortest Path, SSSP)를 해결하는 데 사용되며, 다익스트라 알고리즘은 BFS와 달리 가중치 정보를 고려하므로 더 정교하고 현실적인 상황에 적합합니다.

일반적으로 다음과 같은 분야에서 흔히 사용됩니다:

• GPS 내비게이션
• Network 라우팅
• 게임 AI 경로 탐색
• 로보틱스 및 자율주행 시스템
• 지도 서비스에서의 위치 기반 추천

1. 동작 방식

Dijkstra 알고리즘은 탐욕적 방법(Greedy Algorithm)을 기반으로 하며, 다음과 같은 절차로 작동합니다:

• 출발 노드의 거리는 0으로 설정하고, 나머지 모든 노드의 거리는 ∞ (무한대)로 설정합니다.
• 가장 거리가 짧은 노드 (처음에는 출발 노드)를 선택하여 방문합니다.
• 그 노드의 이웃 노드들에 대해 다음을 수행합니다:

1) 현재 노드를 거쳐 가는 경로의 임시 거리를 계산합니다.
2) 그 거리가 현재 알려진 거리보다 짧으면, 거리를 갱신합니다.
3) 해당 노드를 “방문 완료”로 표시합니다.
4) 모든 노드를 방문할 때까지 2)–4) 단계를 반복합니다.

예제 그래프

엣지 리스트(Edge List)로 표현한 그래프:

A -> B (1), A -> C (4)
B -> C (2), B -> D (5)
C -> D (1)
만일 A노드에서 시작해서 다른 모든 노드들에 이르는 최단 경로를 찾으려 한다면 이때 Dijkstra 알고리즘을 이용할 수 있습니다.

2. 파이썬 예제

import heapq

def dijkstra(graph, start):
    # 시작에서 각 노드까지의 거리
    distances = {node: float('inf') for node in graph}
    distances[start] = 0

    # 최단 거리를 찾기위한 우선순위 큐
    queue = [(0, start)]  # (거리, 노드)

    while queue:
        current_distance, current_node = heapq.heappop(queue)

        # 이미 더 좋은 경로를 찾았다면 생략한다.
        if current_distance > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node]:
            distance = current_distance + weight

            # 만일 새로운 경로가 더 최단 거리이면 큐를 업데이트 한다.
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))

    return distances

# 그래프 정의
graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('C', 2), ('D', 5)],
    'C': [('D', 1)],
    'D': []
}

# 알고리즘 실행
start_node = 'A'
shortest_paths = dijkstra(graph, start_node)

# 결과
print(f"Shortest paths from {start_node}:")
for node, dist in shortest_paths.items():
    print(f" - to {node}: {dist}")

결과 설명

Shortest paths from A:
 - to A: 0
 - to B: 1
 - to C: 3   (A -> B -> C)
 - to D: 4   (A -> B -> C -> D)

3. 시간 복잡도 분석

Dijkstra 알고리즘의 시간 복잡도는 구현 방식에 따라 다릅니다:

• 단순 배열 사용 시: O(V²)
• 우선순위 큐(Heapq, 최소 힙) 사용 시: O((V + E) log V)
• Fibonacci Heap 사용 시(이론상): O(E + V log V)

일반적으로 Python에서는 heapq 모듈을 사용하여 최소 힙을 구성하고, 위와 같은 방식으로 구현합니다.

4. 알고리즘의 한계

• 음수 가중치를 가진 그래프에서는 사용할 수 없습니다. (Bellman-Ford 알고리즘을 대신 사용)
• 모든 노드 간 최단 경로가 필요한 경우에는 Floyd-Warshall 알고리즘이 더 적합할 수 있습니다.
• 동적 업데이트가 빈번한 경우에는 다익스트라 알고리즘의 재사용이 어렵습니다.

5. A* 알고리즘과의 비교

A* 알고리즘은 휴리스틱 함수를 사용하여 경로 탐색의 효율을 높이는 방식으로, 특정 목표 노드까지의 경로만을 구할 때 더 빠를 수 있습니다. 반면, Dijkstra 알고리즘은 목적지가 정해지지 않은 경우에도 모든 최단 경로를 찾는 데 적합합니다.

6. 참고 문헌

• Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs." Numerische Mathematik, 1, 269–271.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. MIT Press.
• GeeksforGeeks - Dijkstra’s Algorithm: https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-graph-data-structure/
• Python 공식 heapq 문서: https://docs.python.org/3/library/heapq.html