[24.06.26] 99클럽 코테 스터디 38일차 TIL - 다익스트라

1. 다익스트라

다익스트라 알고리즘은 그래프 이론에서 출발점 노드에서 다른 모든 노드까지의 최단 경로를 찾는 알고리즘이다.

파이썬에서는 heapq를 이용하여 구현할 수 있다. 

 

1.1 동작원리

1. 초기화

• 출발 노드에서 시작하여, 출발 노드의 거리를 0으로 설정한다.
• 나머지 모든 노드의 거리는 무한대로 설정한다.
• 아직 방문하지 않은 노드들의 집합을 유지한다.

2. 반복 과정

• 현재 방문하지 않은 노드들 중 가장 거리가 짧은 노드를 선택한다.
• 선택된 노드와 연결된 모든 인접 노드에 대해, 선택된 노드를 경유하여 인접 노드로 가는 경로가 더 짧으면 해당 경로로 업데이트한다.
• 선택된 노드를 방문한 것으로 표시한다.

 

3. 종료 조건

• 모든 노드를 방문했거나, 더 이상 방문할 수 있는 노드가 없을 때 알고리즘이 종료된다.

 

import heapq

def dijkstra(graph, start):
    # 초기화
    distances = {node: float('inf') for node in graph}
    
    # 출발지점의 거리 초기화 및 우선순위 큐에 출발지점 삽입
    distances[start] = 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': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

# 'A' 노드에서 시작하는 최단 경로 계산
distances = dijkstra(graph, 'A')
print(distances)