다익스트라 알고리즘

그래프 내 특정 노드와 그래프 내 존재하는 모든 노드들 간의 각각 최단 거리를 구하는 알고리즘

 

원리

1. 초기값 세팅. (기준 노드를 0으로 놓고 나머지 노드들까지의 거리를 inf로 설정)

2. 그래프를 순회하며 순회한 노드들을 우선 순위 큐에 거리가 짧은 순으로 쌓음

3. 하나씩 dequeue하면서 해당 노드까지의 거리로 inf를 수정함

4. dequeue한 노드와 연결된 노드들을 우선 순위 큐에 다시 거리가 짧은 순으로 추가

5. 3번의 과정을 반복하면서 중복된 노드들이 있다면 거리값을 더 작은 값으로 수정 (ex. A->b까지 5인데 A->C->B거리가 3이라면 B의 값은 3으로 교체)

6. 우선 순위 큐를 사용하면 우선 순위가 떨어지는(거리가 먼) 노드들의 계산은 뒤로 갈수록 스킵되기에 빠른 계산이 가능함

 

mygraph = {
    'A': {'B': 8, 'C': 1, 'D': 2},
    'B': {},
    'C': {'B': 5, 'D': 2},
    'D': {'E': 3, 'F': 5},
    'E': {'F': 1},
    'F': {'A': 5}
}

import heapq	# 파이썬 우선 순위 큐내장 모듈

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}	# {'A': inf, 'B': inf, 'C': inf, 'D': inf, 'E': inf, 'F': inf}
    distances[start] = 0
    queue = []
    heapq.heappush(queue, [distances[start], start])
    while queue:
        current_distance, current_node = heapq.heappop(queue)	# 구조 분해 할당
        
        if distances[current_node] < current_distance:	# 불필요한 연산 스킵
            continue
            
        for adjacent, weight in graph[current_node].items():
            distance = current_distance + weight	# 이 로직으로 인해 경로를 거칠 때마다 current_distance가 계속 누적되어 계산됨
            
            if distance < distances[adjacent]:
                distances[adjacent] = distance
                heapq.heappush(queue, [distance, adjacent])
                
    return distances

dijkstra(mygraph, 'A')