다익스트라 최단경로 알고리즘

다익스트라 최단 경로 알고리즘

: 그래프에서 여러 개의 노드가 있을 때, 특정 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘

'각 노드에 대한 현재까지의 최단 거리' 정보를 1차원 리스트에 저장하고 더 짧은 거리가 나오면 계속 갱신한다.

이 리스트는 처음에 모두 '무한' int(1e9)로 초기화한다.

구현 순서

구현 순서는 아래와 같다.

 

1. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택해 방문한다.
   이 때 헷갈리지 말아야 할 점은 '방문하지 않은'이라 함은 '출발 노드로부터의 최단 거리를 아직 계산하지 않은', 또는 '그 노드를 거쳤을 때 그 노드와 연결된 다른 노드들의 최단 거리를 계산하지 않은'을 의미한다.
   즉, '다른 노드'를 방문하면서 계산한 그 '다른 노드'를 거쳤을 때 '그 노드'까지의 최단 거리가 리스트에 저장되어있다 해서 이를 '그 노드'를 방문한 것으로 보지 않는다. 이는 '그 노드'를 방문한 것이 아니라, 단순히 '다른 노드'를 방문하면서 그 '다른 노드'를 거쳤을 때의 최단 경로를 계산한 것일 뿐이다.
2. 방문한 현재 노드를 거쳐서 갈 수 있는 다른 노드들을 확인하고, 각각 현재 노드를 거쳐서 갈 경우의 최단 거리가 기존 리스트의 값보다 더 짧으면 갱신한다.

모든 노드를 방문할 때까지 이를 반복한다.

 

방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택할 때 선택된 노드는 '최단 거리'가 완전히 선택된 노드이므로,

더 이상 알고리즘을 반복해도 최단 거리가 줄어들지 않는다.

따라서 한 단계당 하나의 노드에 대한 최단 거리는 확실히 찾는 것이다.

 

다시 말하면, 선택된 노드는 그 이후 단계에서 최단 거리가 갱신될 수가 없다. 왜냐하면 그 이후 단계에서는 해당 단계의 방문 노드를 거쳐서 계산한 거리일 것이므로, 거리가 더 늘어나있을 수밖에 없기 때문이다.

시간 복잡도를 줄이자

1번 단계에서 '최단 거리가 가장 짧은 노드'를 선택하려면 리스트를 한 번 더 순회해야 한다.

출발 노드를 제외한 전체 n-1개의 노드에 대해서 다익스트라 알고리즘을 반복해야 하는데,

그 안에서 또 '최단 거리가 가장 짧은 노드'를 알아내기 위해 리스트를 한 번 더 순회하면

시간복잡도가 최악의 경우 O(V^2)이 되는 문제가 있다.

 

이를 해결하기 위해 힙 heap 자료구조를 사용한다.

힙은 우선순위 큐를 구현하기 위해 사용하는 자료구조이다.

우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다.

따라서 위의 '최단 거리가 가장 짧은 노드'를 선택하기 위해 우선순위를 최단 거리로 두면 굳이 순회할 필요 없이 알아서 가장 짧은 노드를 큐에서 꺼내준다.

 

이를 따로 구현할 필요는 없고 파이썬의 heapq를 사용할 수 있는데, 데이터를 (가치, 물건)으로 묶어서 우선순위 큐에 넣는다.

파이썬의 기본적인 구조인 최소힙을 사용하면 가치가 가장 작은 물건을 우선적으로 꺼내므로,

최단 거리가 가장 짧은 노드를 꺼내야 하는 이 상황에서는 heapq 라이브러리를 그대로 사용하면 된다.

import heapq

queue = []
heapq.heappush(queue, (0, start)) # 큐이름, (가치, 물건)
smallest = heapq.heappop(queue) # 알아서 (가치, 물건)의 가치가 가장 작은 물건을 꺼내줌

개선된 다익스트라 알고리즘 소스코드

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

# 노드의 개수, 간선의 개수 입력받기
n, m = map(int, input().split())

# 시작 노드 번호 입력받기
start = int(input())

# 각 노드 연결 정보를 담은 그래프 리스트 만들기
graph = [[] for i in range(n + 1)] # 인덱스 0은 무시, 1번 노드는 인덱스 1

# 최단 거리 테이블, 무한으로 초기화
distance = [INF] * (n + 1) # 인덱스 0은 무시, 1번 노드는 인덱스 1

# 그래프 리스트 채워넣기 (간선 정보 입력받기)
for _ in range(m):
	a, b, c = map(int, input().split())
    
    # a번 노드에서 b번 노드로 가는 거리는 c
    graph[a].append((b,c))
    


def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start)) # (거리, 노드번호)
    
    # 출발 노드에서 출발 노드까지 거리는 0
    distance[start] = 0
    
    while q: # 큐가 비어있지 않은 동안
    	
        # 최단 거리가 가장 짧은 노드 선택
    	dist, now = heapq.heappop(q)
        
        # 방문한 적 있는지 확인
        if distance[now] < dist: # 방문한 적이 있다면 리스트 값은 이미 최단 거리 확정
            continue
        
        # 연결된 노드들 거리 갱신
        for i in graph[now]:   # i: (연결노드번호, 거리)
            cost = dist + i[1] # 현재 노드를 거쳐서 갈 경우의 최단거리
            
            # 현재 노드를 거쳐서 가는 것이 더 짧다면 갱신
            if cost < distance[i[0]]:
            	distance[i[0]] = cost
                
                # 더 짧은 경로를 찾은 노드 정보들은 우선순위 큐에 넣는다
                heapq.heappush(q, (cost, i[0]))
 
dijkstra(start)

# 출력 - 각 노드로 가기 위한 최단 거리
for i in range(1, n + 1):
	if distance[i] == INF:
    	print("INFINITY")
    else:
    	print(distance[i])

과정은 힙을 쓰지 않았을 때와 똑같고, 단지 최단거리가 가장 짧은 노드를 선택하는 것을 힙을 통해 하며 더 짧은 경로를 찾은 노드 정보들은 힙에 저장해주는 과정만 다르다.

 

1. 최단 거리가 가장 짧은 노드를 방문하고 (heapq.heappop(큐)), 방문한 적이 없는 노드가 맞는지(기존 리스트의 값 > 방금 힙에서 꺼낸 가치) 확인한다.
2. 방문한 현재 노드를 거쳐서 갈 수 있는 다른 노드들을 확인하고, 각각 현재 노드를 거쳐서 갈 경우의 최단 거리가 기존 리스트의 값보다 더 짧으면 갱신한다.

시간복잡도는 O(ElogV)로 개선된다.