[백준] 최단거리 알고리즘 <1 : 다익스트라>
1. 다익스트라 알고리즘이란?
다익스트라 알고리즘(Dijkstra Algorithm)은 최단거리 알고리즘 중 하나이다.
음의 가중치(이때 가중치는 거리라고 생각하면 편하다)가 없는 그래프에서 사용할 수 있다. 알고리즘의 작동방식에 따라 음의 가중치가 있는 경우엔 해당 구간을 무한으로 돌아버려 음수의 무한대의 거리가 나오기 때문에 불가능하다.
시간 복잡도는
$O((V+E)logV)$
가 소요된다. 이는 아래서 알고리즘을 설명할때 같이 계산해보겠다.
2. 알고리즘 설명
아래 문제를 예시로 들어 설명해보겠다.
방향이 주어져있는 가중치(거리)와 그 노드들이 주어진다. 그림으로 표현하면 아래와 같다.
- 주어진 정보들을 1차원 리스트 graph에 graph[시작점] = (도착점, 가중치)의 튜플 형태로 저장한다.
시작점에서부터 해당 인덱스인 노드까지의 거리 리스트를 만든 수 inf로 초기화한다. 이때 초기값이 inf인 이유는 최소거리를 갱신할때 갱신할 값이 원래 값보다 작아야 하기 때문이다.
0 1 2 3 4 5 inf inf inf inf inf inf 시작점의 거리값을 0으로 만든 후, 시작점을 힙큐(우선순위 큐)에 저장한다. 이때 우선순위 큐를 사용하는 이유는 이웃한 노드 중 최소거리를 찾아가기 위함이다. 이때 V개의 노드에서 최소거리를 찾는데에 $O(VlogV)$ 가 소요된다.
0 1 2 3 4 5 inf 0 inf inf inf inf 가중치가 가장 작은 인접한 노드로 이동한 후 가중치와 이전 노드의 거리를 더해준다. 이때, 이 값이 새로 이동한 노드의 distance 값보다 작을 경우 갱신해준다. 이때 각 노드들의 간선(edge)의 수를 E라고 할때, 각 노드 V개마다 최소값으로 갱신해주는데 $O(ElogV)$ 가 소요된다.
0 1 2 3 4 5 inf 0 2 3 inf inf
해당 과정을 while문으로 돌려 우선순위 큐 안에 이동할 노드가 더 이상 없을 경우까지 계속해준다.
위 문제에 대해서 계속해보자면 1번에서 시작한 후 거리를 갱신한 그래프는 위와 같다. 이후 이동할 수 있는 노드들을 힙큐에 저장한 후 가장 거리가 짧은 노드부터 꺼내 이동한다.
이때 1번노드에서 이동 가능한 노드들 중 2번 노드가 3번 노드보다 거리가 짧으므로 먼저 이동한다.
2번 노드에서 이동 가능한 노드는 3번과 4번이다. 이때 3번으로 이동하는 경우가 더 짧으므로 1~2번까지 이동하는 거리 2와 2 ~ 3 노드의 이동거리 4를 더해 3번 거리와 비교한다. 이때 기존값 3이 6보다 짧으므로 새 거리를 갱신하지 않는다.(1 → 2 , 2 → 3 보다 1 → 3 이 짧은 경우이다. )
2에서 4로 이동하면 5의 거리가 소요되고, 이때 4는 inf이므로 7(2 + 5)의 값을 입력한다.
| 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| inf | 0 | 2 | 3 | 7 | inf |
다음 3번 노드에서 이동 가능한 노드는 4번이다. 이때 3번 노드까지의 최소비용 3에 3 → 4의 비용 6이 추가된다. 즉 9(3 + 6)의 비용으로 4번 노드로 이동할 수 있지만, 이미 4번 노드는 7의 비용으로 이동할 수 있으므로 갱신하지 않는다.
| 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| inf | 0 | 2 | 3 | 7 | inf |
4번 노드에서는 그 다음으로 이동할 수 있는 노드가 없으므로 유지한다.
완성된 distance 리스트는 1번 노드에서 출발해 각 노드까지의 최소 비용을 나타낸다. 이때 0번 인덱스는 단순히 index와 노드 번호를 맞추기 위한 dummy 값이므로 무시한다. 즉
1 → 1 은 0의 최소비용이다.
1 → 2 는 2의 최소비용이다. (1 → 2)
1 → 3 은 3의 최소비용이다. (1 → 3)
1 → 4는 7의 최소비용이다. (1 → 2 → 4)
1 → 5는 이동할 수 있는 경로가 없다.
각 노드에서 다음 노드로 이동할때 힙큐를 사용해 최단거리를 이동하는 이유는 다익스트라 알고리즘이 Greedy 알고리즘 기반이기 때문이다. 즉, 부분해가 전체해의 일부가 된다.
위의 예시가 아닌 다른 그림의 예시로 설명해보겠다. 
이 예시에서 A -> F로 최단거리로 이동할때의 경로는
A -> D -> C -> F 이다. (= 25)
이때 A -> C로 이동하는 경로는 2가지로
A -> C (= 30)
A -> D -> C( = 20)
이다. 이때 C까지의 최단경로는 A -> D -> C 이므로 이 최단경로가 전체 경로의 부분해가 되는 것을 볼 수 있다.
3. 코드
해당 과정을 코드로 작성하면 다음과 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import sys
import heapq
import math
read = sys.stdin.readline
node_count, line_count = map(int,read().split())
start = int(read().strip())
graph = [[] for _ in range(node_count + 1)]
for _ in range(line_count):
u, v, w = map(int, read().split())
graph[u].append((v, w))
def dijkstra(start):
distance = [math.inf] * (node_count + 1)
distance[start] = 0
pq = [(0,start)]
while pq:
dist_u, u = heapq.heappop(pq) # 거리, 노드
if dist_u > distance[u]:
continue
for v, w in graph[u]:
new_dist = dist_u + w
if new_dist < distance[v]: # 현재 거리보다 작을 경우 갱신
distance[v] = new_dist
heapq.heappush(pq, (new_dist, v))
return distance
answer = dijkstra(start)
for i in range(1,node_count+1):
if answer[i] == math.inf:
print("INF")
else:
print(answer[i])
사진 출처: 나무위키