용도

구현

그림

다익스트라를 구현하는 방법은 여러 가지가 있지만 가장 효율적인 방법은 [우선순위 큐]를 활용하는 방법이다.

그래프가 그림과 같이 주어져있다.
A 노드에서 출발한다고 가정한다.
이 때 자기 자신으로 가는 최단 거리는 0이고 나머지 노드들에 대해서는 무한대로 초기화를 한다.

• 우선순위 큐에서 팝을 한 게 현재 노드이다.
• 현재 노드는 A이므로 A와 연결된 노드들을 찾아서 거리 테이블을 업데이트 한다.

• 현재 노드는 C
• B와 D로 갈 수 있다.
• B로 가는 경우를 계산해봤을 때 1+5 = 6으로 기존값 8보다 작다.
• 따라서 6으로 업데이트 해준다.
• D로 가는 경우는 1+2 = 3으로 기존값 2보다 크다.
• 따라서 무시한다.

• 현재 노드 D
• E와 F를 업데이트 해준다.

• 현재 노드 E
• 마찬가지 원리로 F까지의 거리를 비교해보았을 때 E를 거쳐 가는 길이 더 짧으므로 갱신을 해준다.

• B는 길이 없으므로 패스

• F는 A와 연결되어 있다.
• 0보다 6+5=11이 크므로 무시

• 현재 A-F 최단 거리가 6으로 표기되어 있다.
• 그런데 현재 A-F 거리는 7이므로 가볍게 무시

• 마찬가지 원리로 무시

이렇게 최종 최단 거리 테이블이 완성되었다.

코드

• 그래프가 딕셔너리 형태로 구성되어 있을 때

import heapq

def dijkstra(graph,start):
	distances = {node:float('inf') for node in graph}
    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
        
        if distance < distances[adjacent]:
        	distances[adjacent] = distance
            heapq.heappush(queue,[distance,adjacent])

	return distances
            
        

부록 - 왜 힙을 사용할까? 🤔

문득 이런 생각이 들었다. 왜 우선순위 큐를 사용해야 시간복잡도가 줄어들까? 무슨 연관이 있지??

위 그림에 집중해보자.

A 노드에서 갈 수 있는건 B,C,D 노드

각각 비용이 8,1,2다.

여기서 최소 비용은 1인 C 노드다.

그렇다면 F 노드로 가는 최소 비용을 고려해봤을 때,

B,C,D 중에서 어느 노드를 거쳐 가는 것이 제일 최소 비용일까?

당연히 C 노드이다. 왜냐하면 거리가 제일 짧기 때문.

따라서, 거리 테이블을 업데이트 할 때마다 지속적으로 최소 비용을 찾아주어야 한다.

다시 말해, A 노드에서 거쳐 갈 수 있는 제일 최소 비용인 C를 선택후 거리 테이블을 업데이트 하고

C에서 거쳐갈 수 있는 길(B와 D)중 최소 비용인 D를 선택한다.

같은 방식으로 모든 노드를 거치며 연결 되어 있는 노드들 중 최소 비용인 노드를 선택해가며 거리테이블을 업데이트 해야 하는데

그 과정에서 최소 비용인 노드를 찾는 과정을 힙으로 구현하면 O(1)에 구현되기 때문에 힙을 쓴다.

만일, 힙을 안 쓰면 연결되어 있는 모든 노드의 개수(최악의 경우 N-1개의 노드를 검사해야함)를 검사해봐야 하기 때문에 O(N)의 시간복잡도가 발생한다.

따라서 힙을 안 쓰면 N개의 노드를 순회하며 그 때마다 N개의 노드 중 최소 비용을 탐색하기 때문에 O(N^2).

힙을 쓰면 N개의 노드를 순회하며 그 때마다 힙에서 팝을 하여 비용을 계산하는데 heappop의 시간복잡도가 O(log N)이기 떄문에 총 O(N*logN)의 시간복잡도가 발생한다.