최단 경로 알고리즘 (2)

개선된 다익스트라 알고리즘

 

저번장의 알고리즘은 시간 복잡도가 O(V^2)으로 노드의 개수가 10,000개를 넘어가는 순간 해결이 어려워졌었다.

하지만 다음의 구현 방법을 이용하면 최악의 경우에도 시간 복잡도 O(E logV)를 보장하여 해결할 수 있다.

여기서 V는 노드 개수 , E는 간선 개수이다.

 

저번 장의 알고리즘에서 최단 거리가 짧으면서 탐색하지 않은 노드를 찾기 위해서 선형적으로 테이블을 탐색해야 했다 => N

이 때 힙 자료구조를 사용하여 최단거리에 대한 정보를 빠르게 찾도록 하자 

힙을 사용하면 선형시간이 아닌 로그시간이 걸리므로 N이 1,000,000 이라면 로그시간에서 약 20 정도로. 속도가 크게 빨라진다.

 

-  파이썬에서 우선순위 큐를 지원하기 위해   PriorityQueue 와 heapq를 사용할 수 있다. 속도면에서 heapq를 권장한다.

-  대부분의 언어에서 우선순위 큐 라이브러리 데이터 묶음의 우선순위는 첫 번째 원소를 기준으로 설정된다.

- 큐를 구현할 때 내부적으로는 최소 힙과 최대 힙으로 구성되된다. ( 최소힙은 "가장 낮은 데이터 먼저 삭제" 최대힙은 그 반대이다. )

- 파이썬 라이브러리에서 기본적으로 최소 힙 구조 이용

- 최소 힙을 최대 힙 처럼 사용하기 위해 우선순위에 해당하는 값에 (-)부호를 잠시 넣고 큐에서 꺼내면서 (-)부호를 빼는 방식의 테크닉을 주로 사용한다.

- 힙을 이용하는 경우 모든 원소를 저장한 뒤 우선순위에 맞게 빠르게 뽑아낼 수 있으므로 우선순위 큐 구현에 적합하다.

 

 

-초기 단계 리스트-

노드 번호	1	2	3	4	5	6
거리	0	무한	무한	무한	무한	무한
우선순위 큐	( 거리 0, 노드 1)

 

- step 1- :    꺼낸 원소 ( 거리 0.  노드 1 )

노드 번호	1	2	3	4	5	6
거리	0	2	5	1	무한	무한
우선순위 큐	(거리 1, 노드 4) ,  (거리 2, 노드 2) ,  (거리 5, 노드 3)

 

-step2- :     꺼낸 원소 ( 거리1,  노드 4)

노드 번호	1	2	3	4	5	6
거리	0	2	1(4) + 3 = 4	1	1(4) + 1 = 2	무한
우선순위 큐	(거리 2, 노드 2) , (거리 2, 노드 5) , (거리4, 노드3)  , (거리 5, 노드 3)

 

-step3- :     꺼낸 원소 ( 거리2, 노드 2)

노드 번호	1	2	3	4	5	6
거리	0	2	4	1	2	무한
우선순위 큐	(거리 2, 노드 5) , (거리4, 노드3)  , (거리 5, 노드 3)

 

-step4- :     꺼낸 원소 (거리2, 노드5)

노드 번호	1	2	3	4	5	6
거리	0	2	2(5) + 1 = 3	1	2	2(5) + 2 = 4
우선순위 큐	(거리4, 노드3)  , (거리 4, 거리 6) , (거리 5, 노드 3)

 

-step5- :      꺼낸 원소 (거리3, 노드 3)

노드 번호	1	2	3	4	5	6
거리	0	2	3	1	2	4
우선순위 큐	(거리:4, 노드 3), (거리 4, 거리 6), (거리 5, 노드 3)

 

-step6- : 노드 3은 중복되므로 (거리 4, 거리 6)의 원소에 대해서만 마지막으로 수행한다.

 

 

저번 장의 알고리즘보다 훨씬 빠르게 동작하고, 데이터의 개수가 N개 일 때, 하나의 데이터 삽입/삭제의 복잡도 O(log n)

앞서 코드와 비교할 때 큐를 이용하므로 get_smallest_node()함수를 작성할 필요가 없다.

 

 

 

 

개선된 다익스트라 알고리즘 코드. py

 

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(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]))                  dijkstra(start)

 

개선된 방식의 알고리즘의 시간복잡도는 O(E log N)으로 훨씬 빠르다.

한번 처리된 노드는 더이상 처리되지 않는다. 노드를 하나씩 검사하는 반복문은 선형탐색이 아니므로 V 이상의 횟수로는 반복되지 않는다.

V번 반복될때마다 한번 꺼낸 요소의 각각 자신과 연결된 간선들을 모두 확인하므로 최대 간선의 개수 E만큼 연산이 수행 가능하다.

 

따라서 전체 알고리즘은 E개의 원소를 우선순위 큐에 모두 넣었다가 모두 빼내는 연산과 매우 유사하다고 볼 수 있다.

힙에 N개의 데이터를 모두 넣고, 모두 빼는 과정은 O(NlogN)이다. 최대 E의 간선 데이터를 힙에 넣었다가 다시 빼는 것으로 볼 수 있으므로 O(E logE)이다.

이 때 중복 간선을 포함하지 않는다면 E는 항상 V^2보다 작다. -> O(Elog V)