최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘으로 길 찾기 문제라고도 불린다. 최단 경로 문제는 보통 그래프를 이용해 해결한다. 코딩테스트에서는 최단 경로를 출력하는 문제보다는 단순히 최단 거리를 출력하는 문제가 많다. 최단 거리 알고리즘에는 다익스트라 최단 경로 알고리즘, 플로이드 워셜, 벨만 포드 알고리즘 등이 있다. 그리고 그리디 알고리즘과 다이나믹 프로그래밍 알고리즘이 최단 경로 알고리즘에 그대로 적용된다.
최단 경로 알고리즘은 한 지점에서 다른 한 지점까지의 최단 경로, 한 지점에서 다른 모든 지점까지의 최단 경로, 모든 지검에서 다른 모든 지점까지의 최단 경로를 구하는 문제로 나뉜다. 각 상황에 맞는 알고리즘이 이미 정립되어 있으므로 각각을 살펴보도록 한다.
1. 다익스트라 최단 경로 알고리즘 (Dijkstra) - 특정 한 지점에서 다른 모든 지점으로
다익스트라는 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 다른 모든 노드로 가는 최단 경로를 구해주는 알고리즘이며, 음의 간선이 없을 때 정상적으로 작동한다. 다익스트라 알고리즘은 기본적으로 그리디 알고리즘으로 분류된다. 매번 비용이 가장 적은 노드를 선택하는 과정을 반복하기 때문이다.
① 출발 노드를 설정한다.
② 최단 거리를 저장하는 리스트(최단 거리 테이블)를 만들어 초기화한다.
③ 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
④ 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
⑤ 모든 노드가 방문처리 될 때까지 3,4번을 반복한다.
말로는 이해가 잘 가지 않을 것이다. 예시를 통해 다익스트라의 동작 원리를 살펴보자. 다음 그래프에서 1번 노드에서 다른 모든 노드로 가는 최단 경로를 구한다고 하자. 초기상태에서는 다른 모든 노드로 가는 최단 거리를 무한으로 초기화한다.
다음으로 1번 노드를 거쳐 다른 노드로 가는 비용을 계산한다. 1 ➔ 2 (거리=2), 1 ➔ 3 (거리=5), 1 ➔ 4 (거리=1) 이 된다.
다음으로 아직 방문하지 않은 노드들 중에서 최단 거리가 가장 작은 4번 노드를 선택한다. 이 4번 노드를 거쳐서 갈 수 있는 노드는 3번과 5번으로 1 ➔ 4 ➔ 3 (거리=4), 1 ➔ 4 ➔ 5 (거리=2)이다. 이는 현재 최단 거리 테이블에 있는 값보다 작으므로 3번과 5번 노드의 최단 거리 값을 각각 4, 2로 갱신한다.
다음으로 아직 방문하지 않은 노드들 중에서 최단 거리가 가장 작은 2번, 5번 중 번호가 작은 노드인 2번을 선택한다. 이 2번 노드를 거쳐서 갈 수 있는 노드는 3번과 4번으로 1 ➔ 2 ➔ 3 (거리=5), 1 ➔ 2 ➔ 4 (거리=4)이다. 하지만 이미 현재 최단거리 테이블에 있는 값이 작으므로 갱신되지 않는다.
다음으로 아직 방문하지 않은 노드들 중에서 최단 거리가 가장 작은 5번을 선택한다. 5번 노드를 거쳐서 갈 수 있는 노드는 3번과 6번으로, 1 ➔ 5 ➔ 3 (거리=3), 1 ➔ 5 ➔ 6 (거리=4)이다. 여기서 1번과 5번을 연결하는 간선은 없지만 편의상 그렇게 표현하고 최단거리 테이블에 있는 1 ➔ 5 (거리=2)를 더해준다고 생각하면 된다. 이번에는 3번과 6번의 최단 거리가 모두 갱신된다.
다음으로 아직 방문하지 않은 노드들 중에서 최단 거리가 가장 작은 3번을 선택한다. 3번 노드를 거쳐서 갈 수 있는 노드는 2번과 6번으로, 1 ➔ 3 ➔ 2(거리=6), 1 ➔ 3 ➔ 6 (거리=8)이다. 하지만 이미 현재 최단거리 테이블에 있는 값이 작으므로 갱신되지 않는다.
다음으로 마지막 남은 6번 노드를 선택한다.
이처럼 다익스트라는 방문하지 않은 노드 중에서 가장 최단 거리가 짧은 노드를 선택하는 과정을 반복하는데, 한 번 선택되고 방문된 노드는 최단 거리가 감소하지 않는다. 즉, 다익스트라는 한 단계 당 하나의 노드에 대한 최단 거리를 확실히 찾는 것으로 이해할 수 있다.
Dijkstra with Python - heapq 사용
다익스트라 알고리즘은 힙 자료구조를 사용하여 O(ElogV) 시간으로 구현할 수 있다. 여기서 V는 정점의 개수, E는 간선의 개수이다. 힙은 우선순위 큐를 구현하기 위해 사용하는 자료구조 중 하나라고 했다. 참고 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다. 따라서 최단 거리가 가장 짧은 노드를 선택하는 과정에서 최소 힙 자료구조를 사용하면 된다.
파이썬의 heapq 라이브러리는 원소로 튜플을 입력받으면 첫 번째 원소를 기준으로 우선순위 큐를 구성한다. 따라서 (최단 거리, 노드 번호) 순서대로 튜플 데이터를 구성해 우선순위 큐에 넣으면 된다. heapq는 데이터의 개수가 N개일 때, 하나의 데이터를 삽입 및 삭제할 때의 시간 복잡도는 O(logN)이다. 따라서 정점의 개수 V개, 간선의 개수 E개 일때 다익스트라는 O(ElogV)의 시간 복잡도를 가진다.
코드로 구현하기 전에 다시 위의 예제를 살펴보자. 먼저 출발 노드를 (거리, 노드번호)의 튜플 형태로 우선순위 큐에 넣는다.
그 다음 우선순위 큐의 첫번째 원소 (거리가 가장 짧은 원소)를 꺼낸다. 그리고 갱신된 다른 (거리, 노드번호)들을 우선순위 큐에 삽입한다. 우선순위 큐에 삽입하면 heapq가 알아서 튜플의 첫 번째 원소(거리)가 작은 순서대로 왼쪽부터 기록한다.
다시 우선순위 큐의 첫번째 원소 (거리가 가장 짧은 원소)를 꺼내고 갱신된 것들을 우선순위 큐에 삽입한다.
다시 우선순위 큐의 첫번째 원소 (거리가 가장 짧은 원소)를 꺼내고 갱신된 것들을 우선순위 큐에 삽입한다. 이때는 갱신된 것이 없기 때문에 우선순위 큐에 어떠한 값도 삽입되지 않는다.
다시 우선순위 큐의 첫번째 원소 (거리가 가장 짧은 원소)를 꺼내고 갱신된 것들을 우선순위 큐에 삽입한다.
다시 우선순위 큐의 첫번째 원소 (거리가 가장 짧은 원소)를 꺼내고 갱신된 것들을 우선순위 큐에 삽입한다. 이때도 갱신된 것이 없기 때문에 우선순위 큐에 어떠한 값도 삽입되지 않는다.
다음으로 (거리:4, 노드:3)이 꺼내지는데 노드 3번은 이미 방문처리된 노드이기 때문에 무시하고 넘어간다.
이어서 원소 거리:4, 노드:6)을 꺼내서 6번 노드에 대해 처리한다.
마지막으로 남은 (거리:5, 노드:3)도 꺼내지만 이미 처리된 노드이므로 무시한다.
이 과정을 heapq를 사용해 구현하면 다음과 같다.
import heapq
import sys
input = sys.stdin.readline
n, m = map(int, input().split()) # 노드의 개수, 간선의 개수를 입력받기
start = int(input()) # 시작 노드 번호를 입력받기
graph = [[] for i in range(n + 1)] # 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정
distance = [INF] * (n + 1) # 최단 거리 테이블을 모두 무한으로 초기화
# (n+1)로 하는 것은 인덱스와 노드 번호를 맞추기 위함
# 모든 간선 정보를 입력받기
for _ in range(m):
a, b, c = map(int, input().split())
graph[a].append((b, c)) # a번 노드에서 b번 노드로 가는 비용이 c라는 의미
# 다익스트라
def dijkstra(start):
q = [] # 우선순위 큐
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 # 거리 테이블 갱신
heap.heappush(q, (cost, i[0])) # 갱신된 데이터 우선순위 큐에 삽입
# 다익스트라 알고리즘을 수행
dijkstra(start)
# 모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, n+1):
if distance[i] == INF: # 도달할 수 없는 경우, 무한이라고 출력
print('INF')
else: # 도달할 수 있는 경우 거리를 출력
print(distance[i])
다익스트라 시간 복잡도: O(ElogV)
여기서 while문은 노드를 하나씩 꺼내 검사하는 것이므로 노드의 개수 V이상의 횟수로는 반복되지 않는다. V번 반복할 때마다 각각 자신과 연결된 간선들은 모두 확인한다. 앞에서 말했듯이 힙에 N개의 데이터를 넣고 뺴는 과정은 O(NlogN)이다. 다익스트라의 시간 복잡도는 최대 E개의 간선 데이터를 힙에 넣었다가 빼는 것으로 볼 수 있기 때문에 O(ElogE)라고 할 수 있다. 여기서 간선의 개수 E는 모든 노드끼리 서로 다 연결되어 있을 때 최대 $V^{2}$ 이기 때문에 전체 시간 복잡도는 O(ElogV)가 된다.
2. 플로이드 워셜 알고리즘 (Floyd-Warshall) - 모든 지점에서 다른 모든 지점으로
플로이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경를 모두 구하는 알고리즘이다. 다익스트라 알고리즘에서는 출발 노드가 1개이므로 다른 모든 노드까지의 최단 거리를 저장하기 위해 1차원 리스트를 사용했다. 하지만 플로이드 워셜은 모든 노드에 대해 다른 모든 노드로의 최단 거리 정보를 담아야 하기 때문에 2차원 리스트를 사용한다. 다시말해 노드의 개수가 N개 일때, N번의 단계에서 매번 $O(N^{2})$의 시간이 소요되어 총 $O(N^{3})$의 시간 복잡도를 가진다.
플로이드 워셜은 N번 만큼 단계를 반복하여 점화식에 맞게 2차원 리스트를 갱신하기 때문에 다이나믹 프로그램으로 볼 수 있다. 각 단계에서는 거쳐 가는 노드를 기준으로 알고리즘을 수행한다. 예를 들어 1번 노드에 대해서 확인할 때는 1번 노드를 중산에 거쳐 지나가는 모든 경우를 고려하면 된다. A 노드 ➔ 1번 노드 ➔ B번 노드로 가는 비용을 확인한 후에 최단 거리를 갱신한다. 따라서 N-1개의 노드중 서로 다른 노드 (A,B)쌍을 선택한다. 다시말해 $(N-1)P(2)$ 개의 쌍을 각 단계마다 반복해서 확인하게 된다. 현재 선택된 노드가 k라면 점화식은 $D_{ab} = min(D_{ab}, D_{ak} + D{kb})$이다. 이는 A에서 B로 바로 가는 거리와 특정 노드 k를 거쳐서 이동하는 거리 중 더 짧은 것으로 갱신한다는 것이다.
① 최단 거리를 저장하는 2차원 리스트(최단 거리 테이블)를 만들어 초기화한다.
② $D_{ab} = min(D_{ab}, D_{ak} + D_{kb})$ 점화식에 따라 최단 거리 테이블을 갱신한다.
③ 모든 노드에 대해 2번을 수행한다.
다음 예시를 통해 동작 방법을 확인해보자. 먼저 초기 테이블을 설정하여 연결된 간선은 그 비용을 채워넣고, 연결되지 않은 간선은 무한이라는 값을 넣는다. 그리고 자기자신으로 가는 비용은 0으로 초기화한다.
첫번째 단계에서는 단순히 1번 노드를 거쳐 가는 경우를 고려한다. 이때는 정확히 3P2 =6 가지의 경우에 대해서만 고려하면 된다. 각 경우에 대해 1을 거쳐 갈때가 더 빠른 경우에만 최단 거리를 갱신하면 된다.
$D_{23} = min(D_{23}, D_{21} + D{13}) = min(7, INF)$
$D_{24} = min(D_{24}, D_{21} + D{14}) = min(INF, 9)$
$D_{32} = min(D_{32}, D_{31} + D{12}) = min(INF, 9)$
$D_{34} = min(D_{34}, D_{31} + D{14}) = min(4, 11)$
$D_{42} = min(D_{42}, D_{41} + D{12}) = min(INF, INF)$
$D_{43} = min(D_{43}, D_{41} + D{13}) = min(2, INF)$
다음 단계에서는 2번 노드를 거쳐 가는 경우 6가지를 고려하면 된다.
다음 단계에서는 3번 노드를 거쳐 가는 경우 6가지를 고려하면 된다.
마지막으로 4번 노드를 거쳐 가는 경우 6가지를 고려하면 된다.
최종적으로 다음과 같은 결과를 얻을 수 있다. 이 테이블은 모든 노드에서 모든 노드로 가는 최단 거리 정보를 표현하고 있다. 예를 들어 1번 노드에서 3번 노드로 가는 최단 거리는 8이다.
Floyd-Warshall with Python - 3중 반복문, 점화식 사용
플로이드 워셜은 점화식과 3중 반복문을 이용해 간단히 구현할 수 있다.
INF = int(1e9)
n = int(input()) # 노드의 개수
m = int(input()) # 간선의 개수
# 2차원 테이블 초기화
graph = [[INF] * (n+1) for _ in range(n+1)] # 모든 값을 무한대로 초기화
for i in range(n+1): # 자기 자신으로 가는 비용은 0으로 초기화
graph[i][i] = 0
for _ in range(m): # 각 간선에 대한 정보 입력받아서 테이블값 초기화
a, b, c = map(int,input().split())
graph[a][b] = c
# 점화식
for k in range(1, n+1):
for a in range(1, n+1):
for b in range(1, n+1):
graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
# 결과 출력
for a in range(1, n+1):
for b in range(1, n+1):
if graph[a][b] == INF:
print('INF', end=' ')
else:
print(graph[a][b], end=' ')
print()
플로이드 워셜 시간 복잡도: $O(N^{3})$
플로이드 워셜 알고리즘은 노드의 개수가 N개 일때, N번의 단계에서 매번 2차원 테이블을 갱신하는 데 $O(N^{2})$의 시간이 소요되어 총 $O(N^{3})$의 시간이 소요된다. 쉽게 생각하면 3중 반복문을 사용했기 때문에 $O(N^{3})$라고 할 수 있다.
정리하면 다익스트라 알고리즘은 특정 노드에서 다른 모든 노드로까지의 최단 거리를 구할 때 사용하며, 우선순위 큐를 이용해 O(ElogV)의 시간으로 구현할 수 있다. 플로이드 워셜 알고리즘은 모든 노드에서 다른 모든 노드로의 최단 거리를 구할 때 사용하며, 3중 반복문과 점화식을 이용해 $O(N^{3})$ 시간으로 구현할 수 있다. 노드의 개수가 적은 경우에는 플로이드 워셜 알고리즘을 사용할 수 있고, 노드와 간선의 개수가 모두 많으면 다익스트라 알고리즘을 사용하는 것이 유리하다.
