[WEEK03] 다익스트라 알고리즘

다익스트라 알고리즘 (Dijkstra Algorithm)

• 다익스트라 알고리즘은 하나의 시작 정점(source)에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이다.
• 그래프 내 모든 간선의 가중치가 0 또는 양수일 때 사용할 수 있다.
• 주로 네트워크 경로 탐색, 지도 서비스, 게임 내 길찾기 등에서 활용된다.

🧩 동작 원리

1. 시작 노드의 거리를 0으로, 나머지 노드의 거리는 무한대(∞)로 초기화
2. 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택
3. 선택된 노드를 통해 연결된 이웃 노드들의 거리 값을 갱신
4. 모든 노드를 방문할 때까지 2~3번 반복

📌 핵심 포인트

• "가장 가까운 노드부터 탐색한다"
• 그리디 알고리즘 기반

🚀 시간 복잡도

• 우선순위 큐(Heap)를 사용하면 O((V + E) log V)
• 단순 배열 사용 시 O(V²) → 노드 수가 많은 경우 비효율적

💻 코드 구현

import heapq

def dijkstra(graph, start):
    # 초기화
    distance = {node: float('inf') for node in graph}
    distance[start] = 0
    queue = [(0, start)]  # (거리, 노드)

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

        # 기존 거리보다 크다면 스킵 (이미 최단 경로로 처리됨)
        if current_dist > distance[current_node]:
            continue

        for neighbor, weight in graph[current_node]:
            cost = current_dist + weight
            if cost < distance[neighbor]:
                distance[neighbor] = cost
                heapq.heappush(queue, (cost, neighbor))

    return distance

# 사용 예시
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)]
}

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

# 실행 결과
# {'A': 0, 'B': 1, 'C': 3, 'D': 4}

🚩 특정 도착 지점이 정해진 경우

• 기본 다익스트라 알고리즘 그대로 사용하면서, 도착 지점까지의 최단 경로가 확정되면 바로 종료하는 방식으로 바꿀 수 있다.
• 다익스트라는 최단 거리 확정 순서가 "거리 순" 이기 때문에, 도착 노드가 처음으로 우선순위 큐에서 나오는 순간 → 이미 최단 경로가 확정된 상태이기 때문이다.

import heapq

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

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

        # 도착 지점에 도달하면 바로 종료
        if current_node == end:
            return distance[end]

        if current_dist > distance[current_node]:
            continue

        for neighbor, weight in graph[current_node]:
            cost = current_dist + weight
            if cost < distance[neighbor]:
                distance[neighbor] = cost
                heapq.heappush(queue, (cost, neighbor))

    return float('inf')  # 도달할 수 없는 경우

# ✅ 사용 예시
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)]
}

result = dijkstra(graph, 'A', 'D')
print(f"A → D 최단 거리: {result}")

# 실행 결과
# A → D 최단 거리: 4

✏️ 정리

• 다익스트라 알고리즘은 우선순위 큐와 함께 사용하면 효율적이다.
• 음수 가중치가 있는 그래프에서는 사용 불가 → 벨만-포드 알고리즘 필요
• 막상 구현해보니 거리 갱신 조건(cost < distance[neighbor]) 부분이 핵심!