1. 다익스트라(Dijkstra) 알고리즘이란
- 음의 가중치가 없는 그래프의 한 정점에서 다른 정점까지의 최단 경로(거리)를 구하는 알고리즘이다.
- 음의 가중치가 있을 때는 벨만-포드 알고리즘을 사용할 수 있다.
- 가능한 모든 노드쌍의 최단 거리를 구할 때는 플로이드-워셜 알고리즘을 사용한다.
- BFS를 기본으로 한다.
2. 다익스트라 알고리즘 동작 방식
- 출발 노드로부터 각 노드까지 최단 경로를 저장할 배열 distance[v]를 초기화하고, 출발 노드의 인덱스에는 0, 다른 노드에는 매우 큰 값을 저장한다(무한에 근접하도록 distance의 원소 타입의 최댓값으로 설정하면 된다).
- 현재 노드를 뜻하는 노드 A에 출발 노드 번호를 저장한다.
- A로부터 갈 수 있는 임의의 노드 B에 대해, A까지 최단거리(distance[A]) + A에서 B까지의 거리(graph[A][B])와 기존에 계산한 B까지의 최단거리(distance[B])를 비교한다. (min(distance[A]+graph[A][B], distance[B])) INF와 비교할 경우 무조건 전자가 작다.
- 만약 전자가 더 작다면, 즉 더 짧은 경로일 경우 distance[B]를 갱신한다.
- A의 모든 인접 노드에 대해 이 작업을 수행한다.
- 모든 인접 노드에 대해 위 작업을 마쳤으면, A를 '방문 완료'로 처리하여 중복 탐색을 방지한다.
- '미방문' 상태인 모든 노드들 중, 출발점으로부터 거리가 가장 짧은 노드를 하나 골라서 그 노드를 A에 저장한다.
- 도착 노드가 '방문 완료' 상태가 되거나, 혹은 더 이상 미방문 상태의 노드를 선택할 수 없을 때까지, 3~7을 반복한다.
이 작업을 마친 뒤, 도착 노드에 저장된 값(distance[end])이 바로 A로부터의 최단 거리이다. 만약 이 값이 INF라면, 중간에 길이 끊긴 것임을 의미한다.
3. 구현(파이썬)
3.1 단순한 방식
def dijkstra(start, n):
infos = [[1, 2, 2], [1, 3, 1], [2, 4, 1], [2, 5, 2], [3, 4, 3], [4, 5, 1], [5, 6, 1]]
INF = 10e9
distance = [INF] * (n + 1)
graph = [[] for i in range(n + 1)]
visited = [False] * (n + 1)
for v, w, u in infos:
graph[v].append((w, u))
for v, w in graph[start]:
distance[v] = w
def get_smallest_node():
smallest_value = INF
index = 1
for i in range(1, n+1):
if distance[i] < smallest_value and not visited[i]:
smallest_value = distance[i]
index = 0
return index
for _ in range(n-1):
now = get_smallest_node()
visited[now] = True
for child in graph[now]:
c_node = child[0]
cost = distance[now] + child[1]
if cost < distance[c_node]:
distance[c_node] = cost이 경우 시간복잡도는 \(O(v^2)\)이다.
3.2 우선순위큐 이용
from collections import defaultdict
import heapq
infos = [[1, 2, 2], [1, 3, 1], [2, 4, 1], [2, 5, 2], [3, 4, 3], [4, 5, 1], [5, 6, 1]]
INF = 10e9
distance = defaultdict(int)
graph = defaultdict(list)
Q = []
for u, v, w in infos:
graph[u].append([v, w])
Q.append((0, start))
while Q:
current_cost, current_node = heapq.heappop(Q)
if distance[current_node] < current_cost:
continue
for child in graph[current_node]:
child_node = child[0]
child_cost = child[1]
alt_cost = current_cost + child_cost
if alt_cost < distance[child_node]:
heapq.heappush(Q, (alt_cost, child_node))
print(distance)
※ 우선순위 큐를 활용한 다익스트라 알고리즘의 시간복잡도
우선순위 큐를 사용할 경우 위 동작방식 7번에서 시간복잡도를 크게 줄일 수 있다.
우선순위 큐를 사용하면 한번 처리된 노드는 더이상 처리되지 않는다. 즉 노드를 하나씩 꺼내 검사하는 반복문(while문)은 노드의 개수 V 이상의 횟수로는 반복되지 않는다. 또한 V번 반복될 때마다 각각 자신과 연결된 간선들을 모두 확인한다. 따라서 현재 우선순위 큐에서 꺼낸 노드와 연결된 다른 노드들을 확인하는 총 횟수는 총 최대 간선의 개수 E만큼 연산이 수행될 수 있다. 일반적으로 힙연산의 시간복잡도는 \(O(logn)\)이고 \(O(logE)\)를 E개의 원소에 대하여 반복하는 것으로 볼 수 있으므로 시간복잡도는 \(O(ElogE)\)로 표현할 수 있다.
이때 중복 간선을 포함하지 않는 경우, E는 항상 V의 제곱보다 작다. 왜나하면, 모든 노드끼리 서로 다 연결되어 있다고 했을 때 간선의 개수를 약 \(V^2\)으로 볼 수 있고 항상 E는 \(V^2\)이하이기 때문이다.
\(O(ElogE)\) <= \(O(ElogV^2)\)이고, \(O(ElogV^2)\)는 \(O(2*ElogV)\)이므로 \(O(ElogV)\)로 표현할 수 있다.
'자료구조와 알고리즘 > 알고리즘' 카테고리의 다른 글
| [알고리즘] BFS(너비 우선 탐색) (0) | 2022.03.14 |
|---|---|
| [알고리즘] DFS(깊이 우선 탐색) (0) | 2022.03.13 |