최단 경로 찾기

최단 경로 알고리즘

최단 경로 알고리즘은 그래프에서 노드 사이의 최단 경로를 찾는 알고리즘이다. 비단 그래프 뿐 아니라 그래프를 활용하는 거리 계산에도 이용되는데, 예를 들어 manifold 상에서 geodesic distance를 구할 때에도 이용된다. 일반적으로 컴퓨터공학과 학부 수준에서 사용되거나 코딩 테스트에서 사용되는 알고리즘은 Dijkstra, Floyd-Warshall 알고리즘이 있다고 한다.

Dijkstra Algorithm

다익스트라 알고리즘^{Dijkstra Algorithm}은 그래프 $\mathcal{G}=(V,E)$ 에서 여러 개의 노드가 있을 때, 특정한 노드에서 다른 노드로 가는 각각의 최단 경로를 구해 최단 거리 테이블을 계산하는 알고리즘이다. 일반적으로 그리디 알고리즘으로 분류되는데, 그 이유는 매번 최소비용의 노드를 선택해 임의의 과정을 반복하기 때문이다. 알고리즘의 전반적인 원리는 다음과 같다.

출발 노드를 설정한다.

최단 거리 테이블을 초기화한다.

방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.

해당 노드를 거쳐 다른 노드로 가는 최단 거리 테이블을 계산한다.

위 과정에서 3과 4번을 반복한다.

다익스트라 알고리즘의 시간 복잡도를 생각해보면, 각 노드들에 대해 연결된 노드를 일일이 확인하는 과정을 거치므로 $O(V^{2})$ 임을 알 수 있다. 그러나, 만일 위 알고리즘에서 3번 과정을 좀 더 효율화한다면, $O(E\log V)$ 까지의 시간 복잡도를 보장할 수도 있다.

$O(E \log V)$ Algorithm

이 알고리즘에서는 힙^heap 자료구조를 사용하는데, 이는 우선순위 큐^{priority queue}를 구현하기 위해 사용하는 자료구조 중 하나이다. 일반적인 스택, 큐 자료구조와는 달리, 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다는 특징이 있다. 파이썬에서는 heapq 모듈을 이용해 이를 구현할 수 있다. 우선순위 큐를 리스트 형태로 구현할 수도 있지만, 아래 표와 같이 시간복잡도에서 유의미한 차이가 발생하게 된다.

구현 방식	삽입 시간	삭제 시간
리스트	$O(1)$	$O(N)$
힙	$O(\log N)$	$O(\log N)$

알고리즘의 소스코드는 다음과 같다.

import heapq
INF = int(1e9) # 최소거리 계산에서 선택되지 않도록 함

# 최단 거리 테이블
distance = [INF] * (n + 1)  # n은 노드 개수

for _ in range(m): # m은 변의 개수
	a, b, c = map(int, input().split())
	graph[a].append((b,c))

# 다익스트라 알고리즘
def dijkstra(start):
	q = []
	heapq.heappush(q, (0, start)) # 시작노드로 가기 위한 최단경로는 0으로 설정
	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]))

Floyd-Warshall Algorithm

플로이드-워셜^{Floyd-Warshall} 알고리즘은 다익스트라 알고리즘과는 달리, 모든 지점에서 서로 다른 지점으로의 최단 경로를 모두 구해야 하는 경우에 사용되는 알고리즘이다. 즉, 각 노드들 간의 최단 경로 행렬을 만들 수 있다. 다익스트라 알고리즘은 1차원 리스트에 최단 거리 테이블을 갱신하였는데, 플로이드 워셜 알고리즘은 2차원 행렬을 기반으로 테이블을 갱신한다. 또한, 플로이드 워셜 알고리즘은 다이나믹 프로그래밍 알고리즘의 일종인데, 이는 노드의 개수가 $V$ 일때, $V$번 만큼의 단계를 반복하여 점화식에 맞게 2차원 행렬($V^{2}$)을 갱신하기 때문이다. 따라서 전체 시간복잡도는 $O(V^3)$ 이 된다. 전체적인 알고리즘의 원리는 다음과 같다.

초기 설정 : 행렬 $D$의 $(n,m)$ 성분 $D_{nm}$은 $n$번째 노드에서 $m$번째 노드까지의 거리를 나타낸다. (연결되지 않은 경우 INF 적용)

$v=1,\ldots,V$ 에 대해 다음과 같은 업데이트를 $V$번 반복한다.

\[D_{nm}=\min(D_{nm},D_{nv}+ D_{vm})\]
즉, 노드 $n$에서 노드 $m$으로 가는 비용보다 $v$번째 노드를 거쳐가는 비용이 더 적다면, 최단거리를 갱신한다는 의미이다.