[파이썬] 최단 경로 찾기 알고리즘 [Algorithm #5]

각 노드 사이의 거리가 다르게 주어졌을 때, 최단 경로를 찾는 알고리즘에는 크게 다익스트라와 플로이드 워셜 알고리즘이 사용된다. 

 

# 다익스트라 알고리즘 : Dijkstra Algorithm

다익스트라는 시작 노드에서 출발하여, 거리가 가까운 노드부터 차례대로 방문하여 해당 노드를 거쳤을 때의 거리가 더 짧으면 최단 거리를 갱신하는 알고리즘이다.

 

N개의 노드가 있다면 N개의 노드에 대해 N-1개의 노드를 확인해야 하므로 O(N^2)의 복잡도를 가진다. 

하지만 heapq를 이용한 우선순위 큐를 쓰면 O(ElogN)까지 낮출 수 있다.

 

(거리, 노드)로 구성된 튜플을 우선순위 큐에 넣는다. 이렇게 한 뒤, 주변 노드들을 살펴볼 때 Min Heap을 이용한 우선순위 큐를 이용하므로 거리가 가장 짧은 원소부터 pop하여 계산하게 된다. 

 

 

# 플로이드 워셜 알고리즘 : Floyd-Warshall Algorithm

앞서 정리한 다익스트라는 모든 경우를 탐색하는 그리디에 해당한다.

다른 방법 중 하나인 플로이드 워셜 알고리즘은 모든 노드들을 돌면서, 각 노드를 거쳐서 갔을 때 더 최단 거리일 경우 갱신하도록 하는 알고리즘이다. 그리디보다는 동적계획법(Dynamic Programming)에 가깝다.

 

예를 들어 5개의 노드가 있고 1번 노드부터 살펴 본다고 할 때, 1번 노드를 제외한 나머지 4개의 노드들에 대해서 1번 노드를 거쳤을 때 최단 거리가 되는 값을 갱신한다. 만약 2번에서 3번으로 가는 거리보다 2번 => 1번 => 3번처럼 1번 노드를 거쳐 가는 거리가 더 짧다면, 해당 거리 배열 값을 갱신한다. 

 

시간 복잡도는 O(N^3)에 해당한다.