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

다익스트라 알고리즘 (Dijkstra's Algorithm)은 그래프에서 단일 시작 정점에서 모든 다른 정점까지의 최단 경로를 찾는 알고리즘입니다. 가중치가 있는 그래프에서 음수 가중치가 없는 경우에 사용됩니다.

알고리즘 동작 원리

1. 시작 정점에서의 거리 초기화:
   • 시작 정점의 거리를 0으로 설정하고, 나머지 모든 정점의 거리를 무한대로 설정합니다.
2. 최단 거리 확정:
   • 현재 확인한 정점 중 최단 거리인 정점을 선택하고 해당 정점의 거리를 확정합니다.
3. 이웃 정점 거리 업데이트:
   • 선택된 정점과 연결된 정점들의 거리를 업데이트합니다.
4. 반복:
   • 모든 정점의 거리가 확정될 때까지 위 과정을 반복합니다.

필요한 자료 구조

• 우선순위 큐(Priority Queue):
  • 최단 거리를 가진 정점을 효율적으로 찾기 위해 사용합니다.
  • Python에서는 heapq를 사용해 최소 힙으로 구현.

다익스트라 알고리즘 구현

1. 인접 리스트를 사용한 구현

import heapq

def dijkstra(graph, start):
    # 거리 저장 배열 (무한대로 초기화)
    distances = {node: float('inf') for node in graph}
    distances[start] = 0  # 시작 정점의 거리는 0
    
    # 우선순위 큐 (힙)
    pq = []
    heapq.heappush(pq, (0, start))  # (거리, 정점)
    
    while pq:
        current_distance, current_node = heapq.heappop(pq)
        
        # 이미 처리된 정점은 무시
        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(pq, (distance, neighbor))
    
    return distances

2. 그래프 입력 및 실행

# 그래프 정의 (인접 리스트)
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 = 'A'

# 다익스트라 실행
result = dijkstra(graph, start)
print("최단 거리:", result)

실행 결과

최단 거리: {'A': 0, 'B': 1, 'C': 3, 'D': 4}

동작 과정

1. 초기화:
   • distances = {'A': 0, 'B': inf, 'C': inf, 'D': inf}
   • 큐: [(0, 'A')]
2. 정점 A 선택:
   • 인접 정점 B: 거리 1 → 업데이트.
   • 인접 정점 C: 거리 4 → 업데이트.
   • distances = {'A': 0, 'B': 1, 'C': 4, 'D': inf}
   • 큐: [(1, 'B'), (4, 'C')]
3. 정점 B 선택:
   • 인접 정점 C: 거리 3 → 업데이트.
   • 인접 정점 D: 거리 6 → 업데이트.
   • distances = {'A': 0, 'B': 1, 'C': 3, 'D': 6}
   • 큐: [(3, 'C'), (4, 'C'), (6, 'D')]
4. 정점 C 선택:
   • 인접 정점 D: 거리 4 → 업데이트.
   • distances = {'A': 0, 'B': 1, 'C': 3, 'D': 4}
   • 큐: [(4, 'C'), (6, 'D')]
5. 정점 D 선택:
   • 인접 정점 없음.

복잡도 분석

1. 시간 복잡도:
   • O(Elog⁡V):
     • E: 간선의 수 (Edge).
     • V: 정점의 수 (Vertex).
     • 우선순위 큐에서 최소 힙 연산 O(log⁡V)를 사용.
2. 공간 복잡도:
   • O(V+E):
     • 정점 수 V와 간선 수 E에 비례하는 메모리 사용.

응용

• 네트워크 최단 경로: 라우팅 알고리즘.
• GPS 시스템: 도로 네트워크에서 최단 경로 찾기.
• 게임 개발: 맵 탐색 및 이동 경로 계산.