1. 다익스트라 알고리즘이란?

다익스트라(Dijkstra) 알고리즘은 그래프에서 하나의 시작점에서 다른 모든 노드까지의 최단 경로를 찾는 알고리즘입니다. 네비게이션이나 게임 맵에서 최단 경로를 찾는 데 주로 사용됩니다.

적용 조건: 모든 간선의 가중치는 음수일 수 없습니다.

활용 사례:

• 네비게이션 시스템의 경로 안내
• 네트워크에서 최적의 데이터 경로 찾기
• 게임에서 캐릭터의 경로 탐색

2. 작동 원리

다익스트라는 그리디(탐욕적) 접근 방식을 이용해 매 순간 가장 짧은 경로를 선택합니다. 그 과정은 다음과 같습니다:
1. 시작 노드에서 출발해 다른 노드로 이동할 최단 거리를 갱신합니다.
2. 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택해 방문합니다.
3. 선택된 노드와 연결된 다른 노드들의 거리를 갱신합니다.
4. 모든 노드를 방문할 때까지 이 과정을 반복합니다.

3. 시간 복잡도

• 우선순위 큐 사용: O((V + E) log V)
• 배열 사용: O(V^2)
  • 여기서 V는 노드의 개수, E는 간선의 개수입니다.

4. 한계

• 음수 가중치: 다익스트라는 음수 간선을 다룰 수 없으므로, 음수 간선이 있는 경우에는 벨만-포드 알고리즘을 사용해야 합니다.
• 출발점 고정: 특정 출발점에서만 최단 거리를 구할 수 있습니다. 모든 노드 간의 최단 거리를 구하려면 플로이드-와샬 알고리즘을 고려하세요.

5. Python 구현

다음은 Python으로 작성한 다익스트라 알고리즘의 간단한 예시입니다.

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].items():
            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': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

start_node = 'A'
shortest_paths = dijkstra(graph, start_node)
print(f"{start_node}에서 각 노드까지의 최단 거리: {shortest_paths}")

6. 결론

다익스트라 알고리즘은 양수 가중치를 가진 그래프에서 최단 경로를 찾는 매우 효율적인 방법입니다. 그러나 음수 가중치가 있을 경우에는 적합하지 않으며, 모든 쌍 간의 최단 거리를 구할 때는 다른 알고리즘(예: 플로이드-와샬)이 필요합니다. 그래프를 탐색하는 많은 문제에서 다익스트라는 중요한 도구로 활용될 수 있습니다.