6-4. 그래프: 최단 경로 (Dijkstra)

1. Dijkstra 알고리즘의 소개

최단 경로 문제는 그래프 이론에서 매우 중요한 문제입니다. 현실 세계의 다양한 문제를 그래프로 모델링하여 해결할 수 있는데, 특히 "어떤 지점에서 다른 지점까지 가장 짧은 길을 찾는 문제"는 매우 빈번하게 발생합니다. 예를 들어, 네비게이션 시스템에서 최단 경로를 찾는 것, 통신 네트워크에서 데이터 전송 경로를 결정하는 것, 그리고 도시 계획에서 효율적인 도로망을 설계하는 것 등이 있습니다. Dijkstra 알고리즘은 이러한 최단 경로 문제를 해결하기 위한 대표적인 알고리즘 중 하나입니다.

Dijkstra 알고리즘은 네덜란드의 컴퓨터 과학자 Edsger W. Dijkstra에 의해 1956년에 개발되었습니다. 이 알고리즘은 그래프 내의 특정 노드(시작 노드)로부터 다른 모든 노드까지의 최단 거리를 계산합니다. 이때, 그래프의 모든 간선은 음이 아닌 가중치를 가져야 합니다. 즉, 간선의 길이나 비용이 음수일 수 없다는 제약 조건이 있습니다. 음수 가중치가 있는 그래프에서는 Dijkstra 알고리즘을 사용할 수 없고, 다른 알고리즘 (예: Bellman-Ford 알고리즘)을 사용해야 합니다.

Dijkstra 알고리즘은 Greedy 기법을 사용합니다. 이는 각 단계에서 현재까지 알려진 최단 거리가 가장 짧은 노드를 선택하고, 해당 노드를 통해 다른 노드로 가는 거리를 갱신하는 방식으로 진행됩니다. 이러한 접근 방식은 각 단계에서 최적의 선택을 함으로써 전체적인 최적 해를 찾는 데 기여합니다.

2. Dijkstra 알고리즘의 원리

Dijkstra 알고리즘의 핵심 원리는 다음과 같습니다.

1. 초기화: 시작 노드를 제외한 모든 노드까지의 거리를 무한대(∞)로 초기화합니다. 시작 노드에서 자기 자신까지의 거리는 0으로 초기화합니다.
2. 반복: 아직 방문하지 않은 노드 중에서 현재까지 알려진 최단 거리가 가장 짧은 노드를 선택합니다.
3. 거리 갱신: 선택된 노드를 통해 다른 노드로 가는 거리를 계산하고, 기존에 알려진 거리보다 짧으면 거리를 갱신합니다. 이 과정을 선택된 노드의 모든 인접 노드에 대해 반복합니다.
4. 종료: 모든 노드를 방문하거나, 더 이상 갱신할 수 있는 거리가 없을 때 알고리즘을 종료합니다.

이 과정을 통해, 시작 노드로부터 다른 모든 노드까지의 최단 거리를 계산할 수 있습니다.

1) 알고리즘 상세 설명

좀 더 자세히 살펴보겠습니다.

1. 거리 배열 (Distance Array): 각 노드까지의 최단 거리를 저장하는 배열입니다. distance[node]는 시작 노드로부터 node까지의 최단 거리를 나타냅니다. 초기에는 시작 노드를 제외한 모든 노드에 대해 ∞ 값을 할당합니다.
2. 방문 여부 배열 (Visited Array): 각 노드의 방문 여부를 나타내는 배열입니다. visited[node]는 node를 방문했는지 여부를 나타냅니다. 방문한 노드는 더 이상 고려하지 않습니다.
3. 우선순위 큐 (Priority Queue): 최단 거리가 짧은 노드를 효율적으로 선택하기 위해 사용됩니다. 각 노드와 해당 노드까지의 거리를 묶어서 큐에 저장합니다. 우선순위 큐는 최단 거리가 가장 짧은 노드를 먼저 반환하도록 구성됩니다.

알고리즘은 다음과 같이 진행됩니다.

1. 시작 노드를 선택하고, distance[startNode] = 0으로 설정합니다.
2. 시작 노드를 우선순위 큐에 넣습니다.
3. 우선순위 큐가 비어 있지 않은 동안 다음을 반복합니다.
   1. 우선순위 큐에서 최단 거리가 가장 짧은 노드를 꺼냅니다. 이 노드를 current 노드라고 합니다.
   2. current 노드를 방문 처리합니다 (visited[current] = true).
   3. current 노드의 인접 노드들을 순회하면서 다음을 수행합니다.
      1. neighbor 노드까지의 거리를 계산합니다: distance[current] + weight(current, neighbor).
      2. 계산된 거리가 neighbor 노드까지의 현재 최단 거리 distance[neighbor]보다 짧으면, distance[neighbor]를 갱신하고, neighbor 노드를 우선순위 큐에 넣습니다.
4. 우선순위 큐가 비어 있으면 알고리즘이 종료됩니다. distance 배열에는 시작 노드로부터 각 노드까지의 최단 거리가 저장됩니다.

알고리즘의 동작 과정을 시각적으로 이해하면 다음과 같습니다. 위 그림에서 시작 노드는 A입니다. 각 노드까지의 최단 거리를 계속 갱신해나가면서, 최종적으로 모든 노드까지의 최단 거리를 구할 수 있습니다.

3. Dijkstra 알고리즘의 구현

Dijkstra 알고리즘은 다양한 프로그래밍 언어로 구현할 수 있습니다. 여기서는 Python 코드를 사용하여 구현 예시를 보여드리겠습니다.

import heapq

def dijkstra(graph, start):
    """
    Dijkstra 알고리즘 구현.

    Args:
        graph: 그래프를 나타내는 딕셔너리. 각 키는 노드이고, 값은 (인접 노드, 가중치) 튜플의 리스트.
        start: 시작 노드.

    Returns:
        시작 노드로부터 각 노드까지의 최단 거리를 담은 딕셔너리.
    """
    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]:
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

# 예시 그래프 (딕셔너리 형태로 표현)
graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('C', 5), ('D', 10)],
    'C': [('E', 3)],
    'D': [('F', 15)],
    'E': [('D', 8), ('F', 7)],
    'F': []
}

start_node = 'A'
shortest_distances = dijkstra(graph, start_node)
print(f"시작 노드 {start_node}로부터의 최단 거리: {shortest_distances}")

1) 코드 설명

• graph는 그래프를 인접 리스트 형태로 표현합니다. 각 노드는 키, 각 노드에 연결된 (인접 노드, 가중치) 튜플의 리스트는 값으로 표현됩니다.
• distances 딕셔너리는 시작 노드로부터 각 노드까지의 최단 거리를 저장합니다. float('inf')는 무한대를 나타냅니다.
• priority_queue는 heapq 모듈을 사용하여 구현된 최소 힙입니다. 각 요소는 (거리, 노드) 튜플로 구성됩니다. 거리가 우선순위로 사용되어 최단 거리가 짧은 노드를 먼저 처리합니다.
• while 루프는 우선순위 큐가 비어 있을 때까지 반복됩니다.
• heapq.heappop(priority_queue)는 우선순위 큐에서 가장 짧은 거리를 가진 노드를 꺼냅니다.
• for 루프는 현재 노드의 인접 노드를 순회하며, 최단 거리를 갱신합니다.
• heapq.heappush(priority_queue, (distance, neighbor))는 갱신된 거리를 가진 노드를 우선순위 큐에 다시 넣습니다.

4. 시간 복잡도 분석

Dijkstra 알고리즘의 시간 복잡도는 그래프의 표현 방식과 사용되는 자료구조에 따라 달라집니다.

1) 인접 행렬 & 우선순위 큐 미사용

만약 그래프를 인접 행렬로 표현하고, 우선순위 큐를 사용하지 않는다면, 각 노드를 순회하면서 최단 거리를 갱신해야 합니다. 이 경우 시간 복잡도는 $O(V^2)$가 됩니다. 여기서 $V$는 노드의 개수입니다.

2) 인접 리스트 & 선형 탐색

그래프를 인접 리스트로 표현하고, 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선형 탐색으로 찾는다면, 시간 복잡도는 $O(V^2 + E)$가 됩니다. 여기서 $E$는 간선의 개수입니다.

3) 인접 리스트 & 우선순위 큐 (Binary Heap)

가장 일반적으로 사용되는 방법은 그래프를 인접 리스트로 표현하고, 우선순위 큐를 사용하여 최단 거리가 짧은 노드를 효율적으로 선택하는 것입니다. 우선순위 큐로 Binary Heap을 사용하는 경우, 노드를 꺼내고 추가하는 연산은 $O(\log{V})$의 시간 복잡도를 가집니다. 각 노드는 최대 한 번씩 우선순위 큐에 추가되므로, 총 $V$번의 추가 연산이 발생합니다. 또한, 각 간선은 최대 한 번씩 고려되므로, 총 $E$번의 거리 갱신 연산이 발생합니다. 따라서, 전체 시간 복잡도는 $O((V + E) \log{V})$가 됩니다.

4) 인접 리스트 & 우선순위 큐 (Fibonacci Heap)

Fibonacci Heap을 사용하는 경우, 최악의 경우 시간 복잡도를 $O(E + V \log{V})$로 줄일 수 있습니다. 그러나 Fibonacci Heap은 구현이 복잡하고, 실제로는 Binary Heap보다 성능 향상이 크지 않으므로, 일반적으로 Binary Heap을 사용합니다.

따라서, Dijkstra 알고리즘의 시간 복잡도는 일반적으로 $O((V + E) \log{V})$로 간주됩니다. 이는 그래프의 노드 수와 간선 수에 따라 달라지며, 그래프가 희소 그래프 (간선 수가 적은 그래프)일수록 효율적입니다.

5. 우선순위 큐 사용의 중요성

Dijkstra 알고리즘에서 우선순위 큐의 사용은 효율성을 결정하는 핵심 요소입니다. 우선순위 큐는 "가장 짧은 거리를 가진 노드를 빠르게 찾는" 역할을 담당합니다.

• 효율적인 노드 선택: 우선순위 큐를 사용하면 O(1) 또는 O(log V) 시간 안에 최단 거리가 가장 짧은 노드를 찾을 수 있습니다. 우선순위 큐를 사용하지 않고 모든 노드를 선형 탐색하는 경우, $O(V)$ 시간이 소요됩니다.
• 시간 복잡도 감소: 우선순위 큐를 사용하면 Dijkstra 알고리즘의 시간 복잡도를 $O((V + E) \log{V})$로 줄일 수 있습니다. 우선순위 큐를 사용하지 않으면 $O(V^2)$ 또는 $O(V^2 + E)$ 시간이 소요됩니다.
• 대규모 그래프 처리: 우선순위 큐를 사용하면 대규모 그래프에서도 Dijkstra 알고리즘을 효율적으로 실행할 수 있습니다.

6. 예제와 활용

1) 예제

다음과 같은 그래프를 예시로 Dijkstra 알고리즘을 적용해 보겠습니다.

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

1. 초기화:
   • distance[A] = 0
   • distance[B] = ∞
   • distance[C] = ∞
   • distance[D] = ∞
2. A 노드 처리:
   • A에서 B까지의 거리: 2. distance[B] 갱신
   • A에서 C까지의 거리: 3. distance[C] 갱신
   • distance: A:0, B:2, C:3, D:∞
3. B 노드 처리:
   • B에서 D까지의 거리: 2 + 4 = 6. distance[D] 갱신
   • distance: A:0, B:2, C:3, D:6
4. C 노드 처리:
   • C에서 D까지의 거리: 3 + 1 = 4. distance[D] 갱신
   • distance: A:0, B:2, C:3, D:4
5. D 노드 처리: D에 연결된 노드가 없음.

결과적으로, A에서 다른 모든 노드까지의 최단 거리는 다음과 같습니다.

• A: 0
• B: 2
• C: 3
• D: 4

2) 활용 사례

Dijkstra 알고리즘은 다양한 분야에서 활용됩니다.

• 네비게이션 시스템: 지도 상에서 출발지에서 목적지까지의 최단 경로를 찾는 데 사용됩니다.
• 통신 네트워크: 라우팅 프로토콜에서 데이터를 전송할 때 최단 경로를 결정하는 데 사용됩니다.
• 물류 시스템: 창고, 배송 센터, 고객 간의 최적의 배송 경로를 찾는 데 활용됩니다.
• 게임 개발: 게임 맵에서 캐릭터가 이동할 때 최단 경로를 계산하는 데 사용됩니다.
• 도시 계획: 도시 내 도로망을 설계하고 최적화하는 데 활용될 수 있습니다.

7. 주의사항과 트러블슈팅

Dijkstra 알고리즘을 사용할 때 주의해야 할 몇 가지 사항이 있습니다.

• 음수 가중치: Dijkstra 알고리즘은 음수 가중치를 가진 간선이 있는 그래프에서는 제대로 작동하지 않습니다. 이 경우에는 Bellman-Ford 알고리즘을 사용해야 합니다.
• 방향성: Dijkstra 알고리즘은 방향성이 있는 그래프와 방향성이 없는 그래프 모두에서 사용할 수 있습니다.
• 간선 가중치: 간선 가중치는 거리, 비용, 시간 등 다양한 의미를 가질 수 있습니다. 문제의 상황에 맞게 간선 가중치를 설정해야 합니다.
• 오버플로우: 거리를 저장하는 변수의 자료형이 충분히 크지 않으면, 거리 값이 오버플로우되어 잘못된 결과가 나올 수 있습니다. float('inf')를 사용하거나, 큰 숫자를 다룰 수 있는 자료형(예: long long)을 사용하는 것이 좋습니다.
• 그래프 표현: 그래프를 인접 리스트 또는 인접 행렬로 표현할 때, 메모리 사용량과 알고리즘의 성능을 고려하여 적절한 방법을 선택해야 합니다. 일반적으로 희소 그래프에서는 인접 리스트가, 밀집 그래프에서는 인접 행렬이 더 효율적일 수 있습니다.

8. 결론

Dijkstra 알고리즘은 그래프 이론에서 매우 중요한 알고리즘으로, 최단 경로 문제를 효율적으로 해결할 수 있습니다. Greedy 기법을 사용하여 시작 노드로부터 다른 모든 노드까지의 최단 거리를 계산하며, 음이 아닌 가중치를 가진 간선에 대해서만 작동한다는 제약 조건이 있습니다. 우선순위 큐를 사용함으로써 시간 복잡도를 개선할 수 있으며, 네비게이션, 통신 네트워크, 물류 시스템 등 다양한 분야에서 활용됩니다. Dijkstra 알고리즘을 이해하고, 효율적으로 구현하고, 적절한 상황에 적용하는 것은 그래프 이론과 알고리즘 분야에서 중요한 역량입니다.