컴퓨터공학과 학부 수준에서 사용하는 최단 거리 알고리즘은 3가지다.
- 플로이드 워셜 알고리즘
- 벨만 포드 알고리즘
- 다익스트라 알고리즘
이 중에서 다익스트라 알고리즘과 플로이드 워셜 알고리즘이 코딩 테스트에서 가장 많이 등장하는 유형이다. 다익스트라 알고리즘에 대해서 알아보자.
다익스트라 알고리즘
다익스트라 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다.
이 알고리즘은 '음의 간선'이 없을 때 제대로 작동한다. '음의 간선'이란 0보다 작은 값을 가지는 간선을 의미하는데, 현실 세계에서는 0보다 작은 값을 가지는 음의 길은 없으므로 GPS 소프트웨어의 기본 알고리즘으로 채택되곤 한다.
다익스트라 알고리즘의 기본적인 원리는 다음과 같다.
- 출발 노드를 설정한다.
- 최단 거리 테이블을 초기화 한다.
- 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
- 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
3,4번 과정을 반복한다.
다익스트라 알고리즘은 그리디 알고리즘으로 분류할 수도 있는데, 매번 최단 거리가 가장 짧은 노드를 선택하여 비용을 계산하고 갱신하는 과정을 반복하기 때문이다.
다익스트라 알고리즘을 구현하는 방법은 2가지가 있다.
- 구현하기 쉽지만 느리게 동작하는 코드
- 힙을 이용하여 빠르지만 까다로운 코드
세상 모든일이 다 그렇지만 까다로워도 빠른 코드가 훨씬 많이 쓰이고 중요하다. 다익스트라 알고리즘도 그렇다. 하지만 1번 코드도 확실이 이해해야 2번 코드를 사용할 수 있으므로, 두 가지 모두 다 다룰 것이다.
동작 원리
다음과 같은 그래프가 있을 때, 1번 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 문제를 생각해보자.
초기 상태에서는 다른 노드와의 거리를 무한으로 설정 하고, 출발 노드에서 출발 노드는 거리가 0이므로 0으로 만들어준다.
1번 노드에서 다른 노드로 가는 비용을 계산한다. 1번 노드와 연결된 모든 간선을 확인해 보면 된다. 1번 노드와 연결된 간선의 비용은 2, 5, 1인데 현재 거리가 무한으로 설정이 되어 있으므로 각각 새로운 값으로 갱신해준다.
위에서 설명했듯이 다음으로 최단 거리가 가장 짧은 노드를 선택해야 한다. 만약 최단거리가 짧은 노드가 2가지 이상일 경우, 번호가 작은 노드를 선택하는 것이 일반적이다.(결과는 달라지지 않지만 코드가 깔끔하다.) 따라서 4번 노드가 선택이 되고, 4번 노드에 연결된 간선을 또 탐색한다.
4번 노드에 연결된 노드는 3번, 5번 노드다. 그 노드들과의 거리는 4(1+3), 2(1+1)인데, 이 두 값은 기존의 리스트에 담겨 있던 값보다 작으므로 갱신이 된다.
이 과정을 계속 반복하여 모든 노드들을 다 탐색하고 난 최종 테이블은 다음과 같다.
더이상 알고리즘을 반복해도 최단 거리가 감소하지 않는다. 즉, 다익스트라 알고리즘이 진행되면서 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것이다.
1. 간단한 다익스트라 알고리즘
간단한 다익스트라 알고리즘을 구현해보자. 이 알고리즘은 시간 복잡도가 O(V^2) 이다. 여기서 V는 노드의 개수를 의미한다.
각 노드에 대한 최단 거리를 담는 1차원 리스트를 선언하고, 단계마다 방문하지 않은 노드들 중 최단거리가 가장 짧은 노드를 선택 하기 위해 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):
# graph[a][0] = b, graph[a][1] = c
# 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 i
def dijkstra(start):
distance[start] = 0
visited[start] = True # 방문했으니까 True로 바꾸어준다.
for i in graph[start]: # a에서 b까지 거리가 c니까!
distance[i[0]] = i[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):
# 도달할 수 없는 경우, 무한으로출력.
if distance[i] == INF:
print("INFINITY")
else:
print(distance[i])코딩 테스트에의 최단 경로 문제에서 전체 노드의 개수가 5000개 이하면 일반적으로 이 코드로 풀 수 있다. 하지만, 10000개를 넘어가는 문제라면 이 코드로는 문제를 해결하기 어렵다. 그럴 때는 이어서 설명할 알고리즘을 이용해야 한다.
2. 개선된 다익스트라 알고리즘
이 구현 방법은 최악의 경우에도 시간복잡도 O(ElogV) 를 보장한다. 여기서 V는 노드의 개수, E는 간선의 개수를 의미한다.
그렇다면 1번 알고리즘과 차이가 무엇일까?
1번 알고리즘은 최단 거리가 가장 짧은 노드를 찾기 위해 매번 최다 거리 테이블을 탐색해야 했다. 이 과정에서만 O(V) 의 시간이 걸린다. 하지만 이 알고리즘에서는 heap 자료구조를 사용하여 선형 시간이 아닌 로그 시간이 걸리므로 더욱 더 빠르게 찾을 수 있다. heap 자료구조에 대한 설명은 생략한다.
동작 원리는 거의 비슷하나 조금 다른점만 잠깐 설명하면, 경로가 갱신될 때 마다 (거리, 노드 번호) 쌍을 우선순위 큐에 넣어주면 된다.
처음에 우리는 1번 노드를 시작점으로 잡았다. 시작점의 거리는 0이므로 0으로 갱신되어 우선선위 큐에 (1,0)을 넣어주었다. 우선순위 큐에서 노드를 꺼내고, 그 노드와 연결된 간선을 모두 탐색한다. 그러면 갱신 되는 거리가 있을 것이고, 그럴 때마다 큐에 넣는다. 그리고 탐색이 끝나면 다수 큐에서 노드를 꺼낸다. 이 과정을 무한 반복하는 것이다. 어차피 거리가 짧은 순서대로 우선순위 큐에 들어가기 때문에(고유의 특성이다.) 해당 노드를 이미 처리한 적이 있다면 무시하면 된다.
코드로 구현하면 다음과 같다.
#개선된 다익스트라 알고리즘
import heapq
import sys
input = sys.stdin.readline()
INF = int(1e9)
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())
graph[a].append((b,c))
def dijkstra(start):
q = []
# 큐에 추가하는 것 : (거리, 노드)
heapq.heappush(q,(0,start))
distance[start] = 0
# 큐가 빌 때까지 반복.
while q:
# 최단 거리의 노드를 꺼낸다.
dist, now = heapq.heappop()
# 이 아래로는 1번 알고리즘과 원리가 똑같다.
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):
if distance[i] == INF:
print("INFINITY")
else:
print(distance[i])이 알고리즘은 우선순위 큐를 이용한다는 점에서 다른 우선순위 큐 문제 유형과도 비슷하다는 특징이 있다. 따라서 이 알고리즘을 제대로 이해한다면 고급 유형의 문제도 쉽게 접근할 수 있다고 한다. 이 알고리즘 꼭 완벽히 마스터하고 자유롭게 구현할 수 있도록 연습해야겠다.
