다익스트라 알고리즘(Dijkstra Algorithm)
1. 개요
그래프에서 여러개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구하는 알고리즘
특징으로는 음의 간선(거리가 0 이하)가 없을 때 정상적으로 작동한다.
2. 원리
원리를 간단히 살펴보면 다음과 같다.
- 출발 노드 설정
- 최단 거리 테이블 초기화
- 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
- 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
- 위 과정에서 3번과 4번을 반복한다.
3. 사용 예
다음과 같은 그래프가 있을 때 1번 노드에서 다른 노드로 가는 최단 경로를 생각해보자
우선 출발 노드는 문제에서 정해줬으니 테이블 초기화를 하자 테이블은 무한에 가깝게 큰 값으로 초기화 한다. 하지만 정수형으로 표기 가능한 수의 한계가 있기 때문에 10억을 의미하는 int(1e9) 혹은 표준라이브러리에 있는 sys.maxsize 로 초기화 해 준다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 거리 | 0 | 무한 | 무한 | 무한 | 무한 | 무한 |
- step 1
1번 노드를 거처 갈수 있는 다른 노드로 가는 비용을 계산한다. 아래의 그림과 같이 2번, 3번, 4번 노드로 가는 비용은 각각 2 , 5 ,1 이다. 이 때 표에서 각 노드들로 가는 비용은 무한으로 초기화 되어 있기 때문에 각각 최소값으로 갱신 해 준다
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 거리 | 0 | 2 | 5 | 1 | 무한 | 무한 |
visited : 1
- step 2
마찬가지로 방문하지 않은 노드중 거리가 초기 노드로 부터 가장 짧은 노드를 선택해야 한다. 즉, 방문하지 않은 2,3 4번 노드 중 최단거리가 가장 짧은 4번 노드를 선택한다.
다시 테이블에서 최소비용을 갱신하는 과정이 필요한데, 4번 노드가 갈 수 있는 노드인 3번 5번 노드에 대해 거리를 계산 해 보면 4(1 + 3)와 2(1 +1)이다. 이때 테이블에 담긴 값보다 작으므로 테이블을 갱신한다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 거리 | 0 | 2 | 4 | 1 | 2 | 무한 |
visited : 1, 4
- step 3
1번 노드로 부터 2번과 5번 노드까지의 거리가 2이고 최소이다. 이때 어느 노드를 선택해도 되지만 관행적으로 번호가 더 작은 2번 노드를 선택한다.
다시 갱신 작업을 위해 거리 계산을 하면 3번 노드와 4번 노드에 대해 5(2 + 3), 4(2 + 2) 의값을 계산할 수 있다. 이 두 경우 모두 현재 테이블보다 작은 값으로 갱신이 불가능하므로 갱신하지 않고 다음 단계로 진행한다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 거리 | 0 | 2 | 4 | 1 | 2 | 무한 |
visited : 1, 2, 4
- step 4
방문하지 않은 노드중 최소 거리인 5번 노드가 선택된다. 이때 3번 6번 노드 까지의 거리는 3(2 + 1),4(2 + 2)이다. 이때 테이블의 있는 값보다 계산한 거리가 더 작으므로 테이블을 갱신해 준다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 거리 | 0 | 2 | 3 | 1 | 2 | 4 |
visited : 1, 2, 4, 5
- step 5 3번 노드에 대해 동일과정을 반복한다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 거리 | 0 | 2 | 3 | 1 | 2 | 4 |
visited : 1, 2, 3, 4, 5
- step 6
마지막으로 6번 노드에 대해 같은 과정을 반복한다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 거리 | 0 | 2 | 3 | 1 | 2 | 4 |
visited : 1, 2, 3, 4, 5, 6
다익스트라 알고리즘은 방문하지 않은 노드에 대하여 최단 거리가 짧은 노드를 선택하는 과정을 반복하는데 모든 노드에 방문 하였으므로 최단거리 테이블이 더이상 갱신할 수 없는 상태이며 최적의 상태이다.
4. 구현
간단한 다익스트라 알고리즘
- 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 매 단계마다 1차원 테이블의 원소를 확인(순차 탐색)함
import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정
# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())
# 시작 노드 번호를 입력받기
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
graph = [[] for i in range(n + 1)]
# 방문한 적이 있는지 체크하는 목적의 리스트를 만들기
visited = [False] * (n + 1)
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n + 1)
# 모든 간선 정보를 입력받기
for _ in range(m):
a, b, c = map(int, input().split())
# a번 노드에서 b번 노드로 가는 비용이 c라는 의미
graph[a].append((b, c))
# 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환
def get_smallest_node():
min_value = INF
index = 0 # 가장 최단 거리가 짧은 노드(인덱스)
for i in range(1, n + 1):
if distance[i] < min_value and not visited[i]:
min_value = distance[i]
index = i
return index
def dijkstra(start):
# 시작 노드에 대해서 초기화
distance[start] = 0
visited[start] = True
for j in graph[start]:
distance[j[0]] = j[1]
# 시작 노드를 제외한 전체 n - 1개의 노드에 대해 반복
for i in range(n - 1):
# 현재 최단 거리가 가장 짧은 노드를 꺼내서, 방문 처리
now = get_smallest_node()
visited[now] = True
# 현재 노드와 연결된 다른 노드를 확인
for j in graph[now]:
cost = distance[now] + j[1]
# 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
if cost < distance[j[0]]:
distance[j[0]] = cost
# 다익스트라 알고리즘을 수행
dijkstra(start)
# 모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, n + 1):
# 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
if distance[i] == INF:
print("INFINITY")
# 도달할 수 있는 경우 거리를 출력
else:
print(distance[i])
간단한 다익스트라 알고리즘의 시간 복잡도
다익스트라 알고리즘은 매 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 이 때 간단한 구현에서는 V번에 걸쳐 최단 거리가 가장 짧은 노드를 매번 선형탐색해야 하고 현재노드와 연결된 노드를 매번 확인해야 하기 때문에 O($V^2$) 의 시간복잡도를 가진다.
개선된 다익스트라 알고리즘
하지만 현재 알려진 개선된 다익스트라 알고리즘을 이용하면 노드 V 간선 E 일때 O($ElogV$) 의 시간 복잡도를 보장하는 방안이 있다.
How?
-
가장 짧은 노드를 매번 선형탐색을 하는 대신 우선순위 큐를 이용하면 가장짧은 노드를 탐색하는 시간을 대폭 줄일 수 있다.
-
우선 순위큐로 힙(Heap)을 사용할 시 삽입,삭제 모두 O($logN$)의 시간복잡도를 가지고 있으므로 기존 선형탐색의 시간 복잡도 O(N) 대비 대폭 감소한 시간복잡도를 가진다.
개선된 다익스트라 알고리즘의 구현
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정
# 노드의 개수, 간선의 개수를 입력받기
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())
# a번 노드에서 b번 노드로 가는 비용이 c라는 의미
graph[a].append((b, c))
def dijkstra(start):
q = []
# 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
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)
# 모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, n + 1):
# 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
if distance[i] == INF:
print("INFINITY")
# 도달할 수 있는 경우 거리를 출력
else:
print(distance[i])