다익스트라 알고리즘 Dijkstra Algorithm

다익스트라 알고리즘?

• 그래프의 한 정점에서 모든 정점까지의 최단거리를 구하는 알고리즘
• shortest path problem 최단 경로 문제에서 사용 
• 과정
  • 1. 출발점으로부터의 최단 거리를 저장할 배열 d[v]를 만들고, 출발 노드에는 0을.
        나머지 노드에는 매우 큰 값인 INF를 놓는다.(보통 실무에서는 원소 타입의 최대값으로 지정)
  • 2. 현재 노드를 나타내는 변수 A에 출발 노드의 번호를 저장.
  • 3. A로부터 갈 수 있는 임의의 노드 B에 대해서, d[A] + Path[A][B]와 d[B]의 값을 비교.
  • 4. 만약  d[A] + Path[A][B]가 더 작다면, d[B]를 이 값으로 갱신.
  • 5. A의 모든 이웃노드 B에 대해서 이 작업을 수행.
  • 6. A의 상태는 "방문 완료"로 바꾸며, 더이상 이는 사용 안한다.
  • 7. "미방문"인 노드들중, 출발점으로부터 거리가 제일 가까운 노드를 골라서 A에 저장
  • 8. 모든 노드가 방문 완료가 되거나, 더이상 노드를 선택할수 없을때까지 3~7의 과정을 반복

import heapq # priority queue 사용을 위한 library

# 다익스트라 알고리즘 구현
def dijkstra( graph , start ):
    # 각 노드까지의 최소 거리를 저장할 딕셔너리. 초기에는 무한대 값으로 설정.
    distances = {node: float('inf') for node in graph}
    print(f'초기에 설정한 노드의 거리는 {distances}입니다.')
    distances[start] = 0 # 출발 노드의 거리는 0으로 설정
    print(f'start를 설정한 노드의 거리는 {distances}입니다.')
    
    priority_queue = [ (0,start) ] # 우선 순위 큐 생성. 첫번째 요소로 (거리,노드)를 지정
    print(f'반복을 수행하기 전의 우선순위 큐 출력: {priority_queue}\n')
    
    while priority_queue: # 우선순위 큐가 empty될때까지 반복 
        # 우선 순위 큐에서 가장 작은 거리 값을 가진 노드를 꺼냄
        current_dist , current_node = heapq.heappop( priority_queue ) 
        print(f'-----> 우선순위 큐에서 pop한 데이터..... current_dist is {current_dist} , current_node is {current_node} , 거리는 {distances}')
        if current_dist > distances[ current_node ]: # 현재 노드까지의 거리가 기존에 저장된 거리보다 큰 경우
            continue
        for neighbor , weight in graph[ current_node].items(): # 인접한 노드를 탐색
            distance = current_dist + weight
            if distance < distances[ neighbor]: # 새로 계산한 거리가 기존보다 가까운 경우
                distances[neighbor] = distance # 갱신 
                heapq.heappush( priority_queue , ( distance , neighbor )) # 갱신된 거리를 우선 순위 큐에 넣어줌
        print(f'----------------> 거리는 {distances}    ----> queue : {priority_queue}\n')
    return distances

 

test_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'  # 출발 노드를 A로...
shortest_distances = dijkstra(test_graph, start_node)

print(f"출발 노드 '{start_node}'로부터 각 노드까지의 최단 거리:")
for node, distance in shortest_distances.items():
    print(f"노드 {node}: {distance}")