알고리즘 - 다익스트라 알고리즘(Dijkstra)

*참고 저서 <이것이 취업을 위한 코딩테스트다> 나동빈 저

 

최단 경로 문제 유형에서 가장 많이 사용되는 알고리즘 중 하나로, 특정 노드에 대해 각 노드들까지의

최단 경로를 구하는 알고리즘이다.

다익스트라 알고리즘은 각 간선의 가중치들을 양수로 가정하고 있다. 따라 음의 가중치를 지닌 수가 있을 경우

다익스트라 알고리즘은 제대로 동작하지 않게 된다.

 

다익스트라 알고리즘의 과정은 다음과 같다.

 

1. 출발 노드를 설정한다.

2. 최단 거리 테이블을 초기화한다.

3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.

4.해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.

5. 위 과정에서 3과 4번을 반복한다.

 

최단 거리 테이블은 노드의 개수만큼의 크기를 지니며

출발노드에서의 최단 거리(가중치)를 저장하고 있다.

특징은 그 값이 매번 갱신된다는 것이다.

 

다익스트라 알고리즘을 처음 공부할 시, 그래프와 최단 거리 테이블을 두고 단계별 갱신 사항을 

눈으로 확인하면서 이해하는 것이 빠르다

 

아래 링크에서 연두 버튼을 클릭해 다익스트라 알고리즘(원형/ 개선형)의 과정을

눈으로 차근히 확인할 수 있다.

https://visualgo.net/ko/sssp

 

 

이를 코드로 구현할 시 핵심이 되는 연산 중 하나는 3번 과정

'3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.'이다.

 

가장 짧은 노드를 매번 탐색하는 과정에 의해 다익스트라 알고리즘의 수행시간이 

O(v^2)이 되버린다. (v = 노드의 수)

 

자료구조 중 최소값을 매번 반환하는 데 유리한 것이 바로

최소 힙이다.

최소힙을 사용해 알고리즘을 개선하면 수행 시간을

O(ElogV)로 확연히 줄일 수 있다.

 

개선되 다익스트라 알고리즘은 다음과 같다.

앞서 말한 최소 힙은 파이썬에서 제공하는 heapq를 사용하여 손쉽게 구현할 수 있다.

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)] 
distance = [INF] * (n + 1)

for _ in range(m):
	a, b, c = map(int , input().split())
	graph[a].append((b, c))
    graph[b].append((a, c))

def dijkstra (start):
	q = []
	heapq.heappush(q, (0 , start))
	distance[start] = 0
	while q:
		dist, now = heapq.heappop(q) 
		if distance[now] < dist:
			continue
		for i in graph[now]:
			cost = dist + i[1]
            if cost < distance[i[0]]: 
				distance[i[0]] = cost 
				heapq.heappush(q,(cost,i[0]))

dijkstra(start)

print(distance)