다익스트라 알고리즘이란?
그래프에서 여러 개의 노드가 존재할 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘.
주로 최단 경로를 찾는 문제에서 자주 사용하는 알고리즘이다.
* 다익스트라 알고리즘 동작 원리
- 출발 노드를 설정
- 각 노드의 최단 거리를 기록할 테이블 정의 후, 최단 거리 테이블을 초기화
- 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
- 해당 노드를 거쳐 다른 노드로 가는 간선 비용을 계산하여 최단 거리 테이블을 업데이트
- 위 과정에서 3, 4번을 반복
(단, 음의 간선이 존재하지 않을 때 즉, 간선(edge)의 값이 0 이상의 양수일 때 다익스트라 알고리즘이 정상적으로 동작)
* 동작 원리 상세 설명
1. 출발 노드 설정 및 최단 거리 테이블 초기화
2. 시작 노드인 1번 노드에 인접한 노드들의 거리를 갱신 (최단 거리 테이블 갱신)
3.
3-1) 방문하지 않은 노드들 중에서 최단 거리가 가장 짧은 노드를 선택 > 4
3-2) 1번 노드 방문 처리 및 새롭게 변경된 시작 노드(4)를 기준으로 인접한 노드들의 거리를 갱신
3번 노드의 경우, min(5,1+3) 이라고 되어 있다. 여기서 5는 시작 노드 1번에서 3번 노드로 한 번에 갈 수 있는 거리였다. 그리고 1+3 이라고 되어 있는 부분은 시작노드 1번에서 4번 노드로 가는 거리비용 1 과 4번 노드에서 3번 노드로 가는 거리비용 3을 의미한다. 이 중 거리비용을 최소화하는 경로는 시작노드인 1번에서 3번으로 다이렉트로 한 번에 가는 것보다 4번 노드를 거쳐 3번 노드로 가는 1 -> 4 -> 3 으로 가는 경로가 최단 경로이다.
이와 같이 간선 비용을 계산하여 최단 거리 테이블을 업데이트 해준다.
4. 가장 마지막으로 갱신된 최단 거리 테이블 기준으로, 방문하지 않은 노드 중 가장 거리가 작은 노드를 다음 탐색 노드로 선정 (거리 비용이 동일할 경우에는 노드 번호가 작은 것부터 탐색)
새로 변경된 시작 노드 2에 인접한 노드 (3, 4)의 거리를 갱신한다. 3번 노드의 경우는, 기존의 최단 경로 값인 4와 1번에서 2번 노드로 가는 거리비용 2 와 2번 노드에서 3번 노드로 가는 거리비용 3 을 의미한다. 이때는 기존 최단 경로값이 더 최소값이기 때문에 최단 거리 테이블을 갱신하지 않는다. 4번 노드도 이와 마찬가지로 갱신되지 않는다.
그리고 방문하지 않은 노드 (3, 5, 6) 중 가장 거리가 작은 5번 노드를 다음 탐색 노드로 선정한다.
이런식으로 모든 노드를 한 번씩 탐색하여 다익스트라 알고리즘 과정을 최종적으로 완료한다.
결국 다익스트라 알고리즘은 방문하지 않은 노드 중에서 가장 거리가 짧은 노드를 선택하는 과정을 반복하는 게 핵심
* 다익스트라 알고리즘 구현 방법
방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위한 방법으로는 순차 탐색 & 최소힙 2가지가 있다.
1) 순차 탐색
O(N^2)의 시간 복잡도를 가진다. 총 O(N)번에 걸쳐 가장 짧은 노드를 매번 선형 탐색 해야하고, 현재 노드와 연결된 노드를 매번 일일히 확인해야 하기 때문이다. 따라서 전체 노드의 수가 5,000개 이하라면 순차탐색 방법을 써도 괜찮지만, 그 이상이라면 힙을 사용하는 개선된 다익스트라 알고리즘을 이용하는 것이 좋다.
import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억 설정
# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())
# 시작 노드 번호를 입력받기
start = int(input())
# 노드 방문 여부 확인을 위한 테이블
visited = [False]*(n+1)
# 최단 거리 테이블
distance = [INF]*(n+1)
# 노드 연결정보
graph = [[] for i in range(n+1)]
for _ in range(m):
# a번 노드에서 b번 노드로 가는 비용 c
a,b,c = map(int, input().split())
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]
# 모든 노드에 대해 반복
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 # 최단거리 테이블 갱신
2) 최소힙 (우선순위 큐 자료구조 활용)
파이썬의 heapq 라이브러리는 원소로 튜플을 받으면 튜플의 첫 번째 원소를 기준으로 우선순위 큐를 구성한다. 따라서 (거리, 노드 번호) 순서대로 튜플 데이터를 구성해 우선순위 큐에 넣으면 거리순으로 정렬된다. 이를 통해 거리가 가장 짧은 노드를 선택한다. 힙에서 노드를 꺼냈는데 만약 해당 노드를 이미 처리한적이 있다면 무시하고 아직 처리하지 않은 노드에 대해서만 처리한다.
import heapq
import sys
input = sys.stdin.readline # 빠른 입력
INF = int(1e9) # 무한을 의미하는 값으로 10억 설정
# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())
# 시작 노드 번호를 입력받기
start = int(input())
# 최단 거리 테이블
distance = [INF]*(n+1)
# 노드 연결정보
graph = [[] for i in range(n+1)]
for _ in range(m):
# a번노드에서 b번 노드로 가는 비용c
a,b,c = map(int, input().split())
graph[a].append((b,c))
# 다익스트라 알고리즘(최소힙 이용)
def dijkstra(start):
q=[]
# 시작 노드
heapq.heappush(q, (0,start))
distance[start] = 0
while q:
# 가장 최단거리가 짧은 노드에 대한 정보 꺼내기
dist, now = heapq.heappop(q)
# 이미 처리된 노드였다면 무시
# 별도의 visited 테이블이 필요없이, 최단거리 테이블을 이용해 방문 여부 확인
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]))
개선된 다익스트라 알고리즘의 시간 복잡도는 O(ElogV)이다. 이때 E는 간선의 개수, 는 노드의 개수를 의미한다.
간선의 개수 E가 시간 복잡도에 관여하는 이유로는,
위 소스코드를 보면 우선순위 큐에서 꺼낸 노드를 탐색할 때, 해당 노드와 연결된 노드들만 탐색하므로 최악의 경우라도 총 간선의 개수인 E만큼을 반복하게 된다. 따라서 E개의 간선을 힙에 넣었다 빼는 것으로 볼 수 있으므로 O(ElogE)가 되게 된다. (힙에서 삽입, 삭제 시간복잡도는 O(logN)이다.)
logE < log(V^2)이고, log(V^2)은 2logV이기 때문에 O(logV)로 표현할 수 있다. 따라서, 다익스트라 알고리즘 전체 시간 복잡도를 O(ElogV) 로 표현할 수 있다.
