알고리즘: 다익스트라(Dijkstra) - 최단 경로 구하기

다익스트라란?

가중치가 양수인 그래프에서,
한 정점으로부터 모든 정점까지의 최단 거리를 구하는 알고리즘.

그래프에서 경로를 탐색하면서, 비용이 최소인 경로부터 차례로 확정해나가는 방식.
우선순위 큐(힙)를 사용하면 매우 효율적으로 구현이 가능하다.

전제 조건

조건	설명
그래프 종류	방향 / 무방향 모두 가능
간선 가중치	음수를 제외한 모든 가중치 가능
목적	단일 시작점에서부터 모든 노드까지의 최단 거리 (One-To-All)

우선순위 큐가 아닌 배열 기반으로 코드를 구성하면 $O(V^{2})$로 매우 느리지만, 우선순위 큐를 기반으로 코드를 구성하면 $O(E\log{V})$로 빠르다.

간선에 음수 가중치가 있다면 다익스트라는 사용할 수 없다.

동작 과정

다익스트라는 다음 과정을 반복하며 최단 거리를 확정한다.

1. 시작 노드의 거리를 0으로 설정하고, 나머지는 무한대로 초기화한다.
2. 우선순위 큐에 (거리, 노드) 형태로 삽입한다.
3. 큐에서 거리가 가장 짧은 노드를 꺼낸다.
4. 해당 노드에서 인접한 노드를 탐색하며, 더 짧은 거리로 도달 가능한 경우, 거리 배열을 갱신하고 큐에 넣는다.
5. 모든 노드가 처리될 때까지 반복한다.

그림으로 보면 다음과 같다.

순서	그래프 이미지
1
2
3
4
5
6
7

음수 가중치가 있는 경우

다익스트라는 "먼저 방문한 경로가 최단 거리"라는 가정을 전제로 한다.
하지만 음수 가중치가 있는 경우, 이 가정이 깨질 수 있다.

단순히 음수 가중치가 있다고 동작하지 않는것은 아니다.
하지만, 음수 간선 자체가 더 짧은 경로가 나중에 등장하는 상황을 만들수도 있다.

-> 따라서 음수 가중치가 있는 경우엔 벨만-포드 알고리즘을 사용해야 한다.

추가로, 그래프 내에 음수 사이클이 존재한다면 거리가 무한히 작아져 다른 알고리즘도 계산이 불가능하다.

구현

위 과정을 생각하며 코드를 구현해보자.
대표적인 다익스트라 문제인 #1753. 최단경로를 봐보자.

시작점에서 다른 모든 정점으로의 최단 경로를 구하는 전형적인 다익스트라 알고리즘 문제이다.
하나씩 구현을 해보겠다.

from heapq import heappop, heappush

def dijkstra(graph: dict, start: int) -> list:
	# 1. 시작 노드의 거리를 0으로 설정하고, 나머지는 무한대로 초기화한다.
	dist = [float("inf")] * 6		# 노드 번호가 1번부터 시작하므로 0번 인덱스는 사용하지 않음
	dist[start] = 0
	# 2. 우선순위 큐에 (거리, 노드) 형태로 삽입한다.
	pq = [(dist[start], start)]
	# 5. 모든 노드가 처리될 때까지 반복한다.
	while pq:
		print("heapq (거리, 노드):", pq)
		# 3. 큐에서 거리가 가장 짧은 노드를 꺼낸다.
		d, n = heappop(pq)
		if d > dist[n]: continue	# 현재 거리가 거리 배열에 저장된 거리보다 크다면 탐색할 필요가 없음.
		# 4. 해당 노드에서 인접한 노드를 탐색하며, 더 짧은 거리로 도달 가능한 경우, 거리 배열을 갱신하고 큐에 넣는다.
		for nn, cost in graph[n]:
			nd = d + cost
			if nd < dist[nn]:
				dist[nn] = nd
				heappush(pq, (nd, nn))
	return dist

heapq 라이브러리를 사용하여 pq 리스트에 최소힙 형태로 저장한다.

이후 큐가 빌때까지 위 과정을 무한반복하게 된다.

이후 반환되는 거리 배열을 출력해보면 테스트 케이스에 나와있는대로 값이 나오는 것을 알 수 있다.