💡 다익스트라 알고리즘이란?
그래프를 이용한 알고리즘으로 최단 경로를 구하는 대표적인 알고리즘 중에 하나이다. 다익스트라가 만들어서 다익스트라 알고리즘이다. 하나의 특정 노드에 대해서 모든 노드까지의 최단 경로를 알 수 있으며 다음과 같은 특징이 있다.
- 가중치가 음수이면 안된다. -> 가중치의 합을 비교하는 알고리즘이기 때문에
- 그리디 알고리즘에 해당한다. -> 매 상황에서 비용이 가장 작은 경로와 노드를 선택하기 때문에
- 단계를 거치며 한 번 처리된 노드의 최단 거리는 변하지 않는다.
📝 간단한 구현
다익스트라 알고리즘을 간단하게 구현해보면, 총 3개의 데이터를 저장할 자료구조가 필요하다. 먼저 어떤 노드에 인접한 노드와 가중치를 저장할 graph 배열, 해당 노드의 방문 처리를 위한 visited 배열, 최단 거리를 저장할 distance 배열이다.
다익스트라 알고리즘은 다음과 같은 순서를 반복한다.
1. 시작노드(start라고 하자)에 대해서 방문처리 및 인접 노드의 최단 거리를 갱신한다.
2. 방문처리가 안된 노드 중 최단 거리가 가장 짧은 노드(now라고 하자)를 선택하고 방문처리 해준다.
3. 시작노드(start)로부터 해당 노드(now)를 거쳐 해당 노드의 인접한 노드까지의 거리와 기존의 distance에 저장되어 있는 시작노드부터 해당 노드와 인접한 노드의 거리를 비교하여 최솟값을 갱신해준다.
예를 들어, A(start)->C가 8인데 A(start)->B(now)가 2이고 B->C(now에 인접한 노드)가 3이면 A->C보다 A->B->C가 더 가까우므로 A->B->C값을 distance에 갱신해준다.
import sys
input = sys.stdin.readline
V, E = map(int, input().split())
S = int(input())
INF = 10000000
# 인접 노드를 저장하는 배열
graph = [[] for _ in range(V+1)]
# 노드 방문 여부
visited = [False]*(V+1)
# 최단 거리 저장하는 배열
distance = [INF]*(V+1)
for _ in range(E):
U, E, W = map(int, input().split())
graph[U].append((E, W))
# 방문 처리가 안된 노드 중 가장 최단 거리가 짧은 노드를 찾는 함수
def get_smallest_node():
min_value = INF
temp_index = 0
for i in range(V+1):
if visited[i] == False and min_value > distance[i]:
min_value = distance[i]
temp_index = i
return temp_index
# 다익스트라 알고리즘을 실행하는 함수
def dijsktra(start):
distance[start] = 0
visited[start] = True
# start노드에 인접한 노드들의 최단거리 갱신
for i in graph[start]:
distance[i[0]] =i[1]
# 시작 노드를 제외한 V-1개의 노드를 방문해야 하므로 V-1번 반복
for _ in range(V-1):
# 최단 거리가 가장 작은 노드를 now에 저장
now = get_smallest_node()
# 방문처리
visited[now] = True
# now에 인접한 노드들을 돌면서 최단 거리 갱신
for i in graph[now]:
if distance[i[0]] > distance[now] + i[1]:
distance[i[0]] = distance[now] + i[1]
dijsktra(S)
for i in range(1, V+1):
if distance[i] == INF:
print("INF")
else:
print(distance[i])💡 효율적인 구현
그런데 위의 코드는 최대 노드의 개수가 적을 때에만 OJ시스템에서 통과될 가능성이 높다. 시간복잡도가 O^2이기 때문이다. 효율적인 다익스트라 알고리즘을 짜기 위해서는 방문처리가 안된 노드 중 가장 최단 거리가 짧은 노드를 찾는 방식을 우선순위 큐를 이용하는 방식으로 바꾸면 된다.
import sys, heapq
input = sys.stdin.readline
V, E = map(int, input().split())
S = int(input())
INF = 10000000
# 인접 노드를 저장하는 배열
graph = [[] for _ in range(V+1)]
# 최단 거리 저장하는 배열
distance = [INF]*(V+1)
for _ in range(E):
U, E, W = map(int, input().split())
graph[U].append((E, W))
# 다익스트라 알고리즘을 실행하는 함수
def dijsktra(start):
distance[start] = 0
priority_q = []
heapq.heappush(priority_q, (0, start))
while priority_q:
dist, now = heapq.heappop(priority_q)
# 이미 최단거리가 확정된 상태이므로 우선순위큐에 넣을 필요가 없다.
# 이 부분이 간단한 부분의 visited배열을 대체한다.
if dist > distance[now]:
continue
for i in graph[now]:
if dist + i[1] < distance[i[0]]:
distance[i[0]] = dist + i[1]
heapq.heappush(priority_q, (distance[i[0]], i[0]))
dijsktra(S)
for i in range(1, V+1):
if distance[i] == INF:
print("INF")
else:
print(distance[i])관련 문제 및 강의
