🗺️ 다익스트라(Dijkstra) 알고리즘: 최단 경로 찾기

📚 다익스트라(Dijkstra) 알고리즘이란?

다익스트라 알고리즘은 그래프에서 특정 시작점으로부터 다른 모든 정점(노드)까지의 최단 경로를 찾는 알고리즘입니다. 특히, 간선(edge)의 가중치(weight)가 음수가 아닌 경우에만 정확하게 동작한다는 중요한 특징이 있습니다.

쉽게 말해, 내비게이션 앱에서 “여기서부터 저기까지 가장 빠른 길은 어디야?”라고 물었을 때, 그 최단 경로를 찾아주는 것과 비슷한 역할을 한다고 생각하시면 됩니다.

💡 주요 개념

그래프(Graph): 정점(노드)과 그 정점들을 잇는 간선으로 이루어진 자료구조입니다.
정점(Vertex/Node): 그래프를 구성하는 점들입니다. (예: 도시)
간선(Edge): 정점들을 연결하는 선입니다. (예: 도시와 도시를 잇는 도로)
가중치(Weight): 간선에 부여된 값으로, 거리가 될 수도 있고, 시간이 될 수도 있습니다. (예: 도로의 길이, 통행 시간)
최단 경로(Shortest Path): 시작 정점에서 목표 정점까지 가중치의 합이 가장 작은 경로입니다.

🚀 다익스트라 알고리즘 동작 방식 (단계별 설명)

다익스트라 알고리즘은 그리디(Greedy) 방식을 사용하며, ‘가장 가까운 곳부터 방문하여 최단 거리를 확정해 나간다’는 아이디어를 기반으로 합니다.

초기화 (Initialization):
- 시작 정점에서 자기 자신까지의 거리는 0으로 설정합니다.
- 시작 정점에서 다른 모든 정점까지의 거리는 무한대(∞)로 설정합니다.
- 아직 방문하지 않은 정점들을 관리할 집합(또는 우선순위 큐)을 만듭니다.
가장 가까운 정점 선택 (Select Closest Vertex):
- 아직 방문하지 않은 정점들 중에서 현재까지 계산된 거리가 가장 짧은 정점을 선택합니다.
방문 처리 (Mark as Visited):
- 선택된 정점을 ‘방문한 정점’으로 표시하고, 이 정점까지의 최단 거리를 확정합니다.
거리 갱신 (Relaxation):
- 선택된 정점을 통해 갈 수 있는 모든 인접 정점들을 살펴봅니다.
- 만약 ‘시작 정점 → 현재 정점까지의 거리 + 현재 정점 → 인접 정점까지의 거리’가 ‘시작 정점 → 인접 정점까지의 현재 거리’보다 짧다면, 인접 정점의 거리를 더 짧은 값으로 갱신합니다. (이 과정을 ‘이완(Relaxation)’이라고 합니다.)
반복 (Repeat):
- 모든 정점을 방문하거나, 더 이상 방문할 수 있는 정점이 없을 때까지 2~4단계를 반복합니다.

⚠️ 중요한 특징 및 제한 사항

음수 가중치 불가: 다익스트라 알고리즘은 간선의 가중치가 음수인 경우에는 올바른 최단 경로를 찾지 못합니다. 음수 가중치가 있는 경우에는 벨만-포드(Bellman-Ford) 알고리즘 등을 사용해야 합니다.
그리디 알고리즘: 매 순간 최적의 선택(가장 가까운 정점 선택)을 통해 전체 최적해(최단 경로)를 찾아냅니다.
효율성: 일반적으로 우선순위 큐를 사용하여 구현할 경우, 시간 복잡도는 O(E log V) 또는 O(E + V log V) (V는 정점의 수, E는 간선의 수)로 효율적인 편입니다.

💻 파이썬 구현 예시

다음은 다익스트라 알고리즘을 파이썬으로 구현한 간단한 예시입니다. heapq 모듈을 사용하여 우선순위 큐를 구현합니다.

import heapq

def dijkstra(graph, start):
    """
    다익스트라 알고리즘을 사용하여 시작 노드로부터 다른 모든 노드까지의 최단 거리를 계산합니다.

    Args:
        graph (dict): 그래프를 인접 리스트 형태로 표현한 딕셔너리.
                      예: {'A': {'B': 10, 'C': 30}, 'B': {'C': 5, 'D': 20}}
        start (str): 시작 노드.

    Returns:
        dict: 시작 노드로부터 각 노드까지의 최단 거리를 담은 딕셔너리.
    """
    # 1. 거리 정보 초기화: 모든 노드까지의 거리를 무한대로 설정하고, 시작 노드는 0으로 설정
    distances = {node: float('inf') for node in graph}
    distances[start] = 0

    # 2. 우선순위 큐 초기화: (거리, 노드) 형태로 시작 노드를 추가
    # heapq는 기본적으로 최소 힙(min-heap)이므로, 거리가 가장 짧은 노드가 먼저 나옴
    priority_queue = [(0, start)]

    while priority_queue:
        # 3. 우선순위 큐에서 가장 거리가 짧은 노드를 가져옴
        current_distance, current_node = heapq.heappop(priority_queue)

        # 4. 이미 처리된 노드이거나, 현재 경로가 더 길다면 건너뜀
        # (이전에 더 짧은 경로로 이미 방문한 경우)
        if current_distance > distances[current_node]:
            continue

        # 5. 현재 노드와 연결된 인접 노드들을 탐색
        for neighbor, weight in graph[current_node].items():
            # 6. 현재 노드를 거쳐 인접 노드로 가는 새로운 거리 계산
            distance = current_distance + weight

            # 7. 새로운 거리가 기존에 알려진 인접 노드까지의 거리보다 짧으면 갱신
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                # 8. 갱신된 거리와 함께 인접 노드를 우선순위 큐에 추가
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

# --- 예시 그래프 정의 ---
graph = {
    'A': {'B': 10, 'C': 30},
    'B': {'C': 5, 'D': 20},
    'C': {'D': 10},
    'D': {} # D는 다른 노드로 가는 간선이 없음
}

# --- 다익스트라 알고리즘 실행 ---
start_node = 'A'
shortest_paths = dijkstra(graph, start_node)

# --- 결과 출력 ---
print(f"시작 노드 '{start_node}'로부터의 최단 경로:")
for node, distance in shortest_paths.items():
    print(f"  {start_node} -> {node}: {distance}")

✅ 마무리

다익스트라 알고리즘은 최단 경로 문제를 해결하는 데 있어 가장 기본적이면서도 중요한 알고리즘 중 하나입니다. 특히 음수 가중치가 없는 그래프에서 그 효율성을 발휘합니다