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

[알고리즘] 다익스트라 알고리즘(Dijkstra)이란?

 

이전에는 다익스트라 알고리즘이 무엇인지 알아보았고

이번에는 다익스트라 알고리즘을 개선해보겠다.

 

다익스트라 알고리즘은 그리디(Greedy) 알고리즘을 기반으로 한다. 현재 상황에서 최적의 해를 구하는 것이다. 

 

 

 

차가 A에서 각 노드로 가는 최단거리를 구한다고 가정해보자. 

A에서 출발한 차가 B일때, C일때, D일때... 각 노드별 최단거리를 구해야 한다.

 

이는 두 과정이 필요하다.

 

1) 모든 노드를 탐색해야 한다. ( O(V) ) 

2) 차가 이동할 다음 노드는  비용이 최소인 노드여야 하므로 최소비용인 노드를 탐색한다. ( O(V) )

 

즉, 이중for문이 만들어진다.

 

 

 

시간복잡도가 O(V²)이다.

원리는 동일하지만 자료구조를 바꾼다면 성능을 개선할 수 있다.

 

우선순위 큐란? ( Priority Queue)

우선순위 큐의 핵심원리는 힙(heap)이다.

 

힙(heap)은 부모노드가 자식노드보다 항상 크거나 작은 완전이진트리 구조이다. Root 노드에는 최댓값이나 최솟값이 온다. 그래서 힙(heap)은 좋은 성능으로 최댓값과 최솟값을 구할 때 사용하는 자료구조이다.  ( O(logN) ) 다시말해서, 힙(heap)을 이용하면 비용이 최소인 노드를 O(logV) 시간복잡도로 구할 수 있다는 의미이다.

 

힙트리의 최댓값, 최솟값을 활용하려면 우선순위 큐가 필요하다. 

 

큐(Queue)는 먼저 들어온 값이 먼저 나간다.

우선순위 큐(Priority Queue)는 우선순위가 높은 순서대로 나간다.

 

 

 

 

우선순위 : 최솟값

위 큐는 최솟값이 먼저 나간다. 현재 큐에는 3과 8이 들어가 있다. 이때 새로운 값을 PUSH 해보자. 

 

 

 

 

2와 5를 PUSH했다. 힙구조가 깨져버렸다. 우선순위 큐는 가장 최솟값을 맨 앞에 두어야 한다. 그러므로 자료구조를 다시 힙화(heapify)를 해야한다.

 

 

 

힙구조가 다시 형성되었다. POP 명령이 떨어지면 우선순위가 높은 최솟값이 나간다. 굉장히 복잡해보이지만 전부를 코드로 구현할 필요는 없다. 파이썬은 라이브러리( heapq )로 위 기능을 제공한다.

 

 

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

 

개선된 다익스트라 알고리즘은 우선순위 큐를 사용한다.

그럼 우선순위 큐에는 어떤 값이 들어갈까?

 

다익스트라 알고리즘은 그리디(Greedy) 알고리즘을 기반으로 한다. 현재를 기준으로 최적해를 구하는 것으로 현재를 반복할 때마다, 최적해는 계속해서 갱신된다. 

 

※ 최단경로테이블

A	B	C	D	E
0	무한	무한	무한	무한

 

 

 

현재 노드 : A 

 

A는 B, C와 인접한다.

1) A -> B로 가는 최단경로는 5L + 0L (A->A)이다.  ( 5 , B )

2) A -> C로 가는 최단경로는 8L + 0L (A->A)이다.  ( 8, C )

 

 

 

※ 최단경로 테이블

A	B	C	D	E
0	5	8	무한	무한

 

 

최단경로 테이블에 최적해를 갱신하고 우선순위큐에 두 값을 등록한다.

그리고 우선순위가 높은 (5, B)를 POP한다.

 

 

현재 노드 : B

 

B는 C,D와 인접한다. ( A는 이미 방문했다. )

 

1) A->B->C로 가는 최단경로는 3L + 5L(A->B) = 8L이다. 

그러나 C의 최단경로 테이블 값도 8L이다.

최단경로 테이블의 값이 같거나 작으면 우선순위큐에 PUSH하지 않는다.

 

2) A->B->D로 가는 최단경로는 1L + 5L(A->B) = 6L이다.

D의 최단경로 테이블 값은 무한이므로 6L가 더 작다 ( 6, D )

 

 

 

※ 최단경로 테이블

A	B	C	D	E
0	5	8	6	무한

 

 

최단경로 테이블에 최적해를 갱신했다. 그리고 힙화(heapify)하여 

비용이 가장 적은 (6,D)가 먼저 POP 될수 있도록 재배열 한다.

 

이 과정을 반복한다. 

 

큐에 등록되는 데이터는 간선 데이터이다. 큐가 모두 빌때까지 반복되므로 최대 반복횟수는 총 간선의 개수(E)이다.  ( 노드의 개수 : V ) 총 E번 반복하는데, 한번 반복마다 O(logE)으로 힙(heap) 구조를 재배열되므로 개선된 다익스트라 구조의 시간복잡도는 O(ElogE)이다. 두 노드 사이에 두개 이상의 간선이 있는 중복간선이 없는 경우라면, E는 항상 V²보다 작다.

 

그러므로

시간복잡도는 O(ElogV²) -> O(2ElogV) -> O(ElogV)라 할 수 있다.

 

 

코드 구현 (python)

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) :
  node,target,cost = map(int, input().split())
  graph[node].append((target,cost))

#다익스트라 함수
def dijkstra(start) :
  q = [] # 큐가 사용할 공간
  heapq.heappush(q,(0,start))  # Start 데이터 push
  distance[start] = 0 # 최단경로테이블 최적해 갱신

  while q : # 큐가 비어질때까지 반복
    cost,node = heapq.heappop(q) #우선순위가 높은 데이터 POP ( 비용, 현재노드 )
    
    # 이미 방문한 노드인 경우 
    if distance[node] < cost : continue 

    for next in graph[node] :
      next_cost = next[1] + cost
      if next_cost < distance[next[0]] : 
        distance[next[0]] = next_cost #최단경로 테이블 최적해로 갱신
        heapq.heappush(q,(next_cost,next[0])) # 데이터 우선순위큐에 PUSH

#다익스트라 알고리즘 함수 호출
dijkstra(start)

#출력
for i in range(1,n+1) :
  if distance[i] == INF : print("INFINITY")
  else : print(distance[i])

 

 

---

 

참고자료

이것이 취업을 위한 코딩 테스트다 with 파이썬 : 네이버 도서