[Algorithm] Dijkstra - 다익스트라 알고리즘 이해하기

안녕하세요! 오늘은 여러분과 함께 다익스트라 알고리즘에 대해 알아보겠습니다. 다익스트라 알고리즘은 그래프 이론에서 매우 중요한 알고리즘 중 하나로, 처음 접하면 다소 복잡해 보일 수 있지만, 차근차근 따라가다 보면 충분히 이해할 수 있습니다. 다익스트라 알고리즘이 무엇인지, 어떻게 동작하는지, 그리고 파이썬으로 어떻게 구현할 수 있는지 자세히 알아보겠습니다.

다익스트라 알고리즘 개요

다익스트라 알고리즘은 네덜란드의 컴퓨터 과학자 에츠허르 다익스트라(Edsger W. Dijkstra)에 의해 1956년에 고안된 알고리즘입니다. 이 알고리즘은 하나의 시작 노드에서 다른 모든 노드까지의 최단 경로를 찾는 방법을 제공합니다. 특히 가중치가 있는 그래프에서 사용되며, 모든 가중치가 양수인 경우에만 적용됩니다.

알고리즘의 작동 원리

다익스트라 알고리즘의 기본 원리는 다음과 같습니다:

1. 초기화: 시작 노드의 거리를 0으로 설정하고, 다른 모든 노드의 거리는 무한대로 설정합니다. 시작 노드는 출발점이기 때문에 거리를 0으로 합니다.
2. 미방문 노드 선택: 현재 미방문 노드 중에서 가장 작은 거리를 가진 노드를 선택합니다. 이 노드는 현재 가장 짧은 경로로 도달할 수 있는 노드입니다.
3. 거리 갱신: 선택된 노드의 인접 노드들을 탐색하며, 기존 거리보다 짧은 경로가 발견되면 해당 거리를 갱신합니다. 새로운 경로가 기존 경로보다 짧다면, 그 경로로 거리를 업데이트합니다.
4. 노드 방문 완료: 선택된 노드를 방문한 것으로 표시하고, 모든 노드가 방문될 때까지 2번과 3번 과정을 반복합니다. 모든 노드를 방문하면 최단 경로가 계산됩니다.

예시를 통한 이해

예시를 통해 다익스트라 알고리즘의 작동 방식을 더 쉽게 이해할 수 있습니다. 아래에 간단한 그래프를 예로 들어 보겠습니다.

  A --1--> B --2--> C
  |       /        |
  4     3          5
  |   /            |
  v v              v
  D --7--> E --2--> F

이 그래프에서 시작 노드를 A로 설정하고 다른 노드까지의 최단 경로를 찾는 과정을 살펴보겠습니다.

1. 초기화:
   • A: 0 (시작 노드)
   • B, C, D, E, F: ∞
2. 첫 번째 노드 선택 (A):
   • A의 인접 노드 B와 D의 거리를 갱신합니다.
   • B: 1 (A -> B)
   • D: 4 (A -> D)
3. 두 번째 노드 선택 (B):
   • B의 인접 노드 C와 D의 거리를 갱신합니다.
   • C: 3 (A -> B -> C)
   • D: 4 (갱신 없음, A -> D)
4. 세 번째 노드 선택 (C):
   • C의 인접 노드 E의 거리를 갱신합니다.
   • E: 8 (A -> B -> C -> E)
5. 네 번째 노드 선택 (D):
   • D의 인접 노드 E의 거리를 갱신합니다.
   • E: 6 (A -> D -> E)
6. 다섯 번째 노드 선택 (E):
   • E의 인접 노드 F의 거리를 갱신합니다.
   • F: 8 (A -> D -> E -> F)

이 과정을 통해 각 노드까지의 최단 경로를 찾을 수 있습니다.

파이썬으로 구현하기

이제 파이썬을 사용하여 다익스트라 알고리즘을 직접 구현해 보겠습니다. 파이썬의 heapq 모듈을 사용하면 우선순위 큐를 쉽게 구현할 수 있습니다.

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': 7},
    'C': {'A': 4, 'B': 2, 'D': 3, 'E': 5},
    'D': {'B': 7, 'C': 3, 'E': 2},
    'E': {'C': 5, 'D': 2}
}

# 알고리즘 실행
start_node = 'A'
print(dijkstra(graph, start_node))  # 시작 노드 A로부터 다른 모든 노드까지의 최단 거리를 출력합니다.

이 코드는 주어진 그래프에서 시작 노드로부터 다른 모든 노드까지의 최단 경로를 계산합니다.

블록별 설명

import heapq

import heapq

• 이 줄은 Python의 heapq 모듈을 임포트합니다. 이 모듈은 우선순위 큐(priority queue)를 구현하기 위한 함수들을 제공합니다. 우선순위 큐는 다익스트라 알고리즘에서 가장 짧은 거리를 가진 노드를 효율적으로 선택하는 데 사용됩니다.

함수 정의 및 초기화

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

• dijkstra 함수는 두 개의 매개변수를 받습니다: graph (그래프 구조를 나타내는 딕셔너리)와 start (시작 노드).
• distances 딕셔너리는 각 노드의 최단 거리를 저장합니다. 초기에는 모든 노드의 거리를 무한대로 설정하고, 시작 노드의 거리는 0으로 설정합니다.
• priority_queue는 우선순위 큐로, (거리, 노드) 형태의 튜플을 저장합니다. 처음에는 시작 노드만 큐에 추가됩니다.

우선순위 큐 처리

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

• while 루프는 우선순위 큐가 비어 있지 않은 동안 계속 실행됩니다.
• heapq.heappop(priority_queue)는 우선순위 큐에서 가장 작은 거리를 가진 노드를 꺼냅니다. 이 노드는 현재 가장 짧은 경로로 도달할 수 있는 노드입니다.

이미 처리된 노드 무시

        if current_distance > distances[current_node]:
            continue

• 이 조건문은 현재 노드의 거리가 이미 기록된 거리보다 클 경우, 해당 노드를 무시하고 다음 노드를 처리하도록 합니다. 이는 중복 처리를 방지하기 위함입니다.

인접 노드 거리 계산 및 갱신

        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight

• 현재 노드의 모든 인접 노드를 탐색합니다.
• distance는 현재 노드까지의 거리(current_distance)와 인접 노드까지의 가중치(weight)를 더한 값입니다.

최단 거리 갱신

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

• 계산된 distance가 기존 기록된 거리보다 짧을 경우, distances 딕셔너리를 갱신합니다.
• 갱신된 거리와 인접 노드를 우선순위 큐에 추가하여 다음 탐색을 준비합니다.

결과 반환

    return distances

• 모든 노드에 대한 최단 거리를 계산한 후, distances 딕셔너리를 반환합니다.

그래프 정의 및 함수 호출

graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 7},
    'C': {'A': 4, 'B': 2, 'D': 3, 'E': 5},
    'D': {'B': 7, 'C': 3, 'E': 2},
    'E': {'C': 5, 'D': 2}
}

start_node = 'A'
print(dijkstra(graph, start_node))

• graph는 각 노드와 그 노드에 인접한 노드 간의 가중치를 나타내는 딕셔너리입니다.
• start_node는 알고리즘의 시작점을 지정합니다.
• dijkstra 함수를 호출하여 그래프의 시작 노드로부터 다른 모든 노드까지의 최단 거리를 계산하고 출력합니다.

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

다익스트라 알고리즘은 다양한 실제 상황에서 매우 유용하게 사용됩니다:

• 네비게이션 및 경로 탐색: GPS 시스템에서 출발지와 목적지 사이의 최단 경로를 계산합니다.
• 네트워크 라우팅: 데이터 패킷의 최적 경로를 설정합니다. 이는 인터넷 트래픽 관리에서 중요한 역할을 합니다.
• 로봇 경로 계획: 장애물을 피하며 목적지까지의 최단 경로를 찾습니다. 이는 로봇 공학에서 필수적인 기술입니다.
• 물류 및 공급망 최적화: 물품의 이동 경로를 최적화하여 비용을 절감합니다. 이는 물류 산업에서 비용 절감과 효율성을 높이는 데 크게 기여합니다.

이 외에도 많은 응용 사례가 있으며, 다익스트라 알고리즘은 다양한 분야에서 중요한 역할을 합니다. 여러분도 직접 알고리즘을 구현해보고, 다양한 예시를 통해 연습해보세요! 이해가 어려운 부분이 있으면 다시 돌아가서 천천히 따라가며 학습하길 권장합니다. 다익스트라 알고리즘은 매우 강력한 도구이며, 이를 잘 이해하고 사용할 수 있다면 많은 문제를 효율적으로 해결할 수 있습니다.