우선순위 큐와 다익스트라 알고리즘(Dijkstra algorithm)

이번 포스팅에서는 우선순위 큐와 다익스트라 알고리즘에 대해서 작성하려 한다. 

 

사실 다익스트라 알고리즘을 파이썬으로 구현하는 것이 이번 포스팅의 주요 목적이나, 우선순위 큐에 대한 개념을

 

알고 있어야 다익스트라 알고리즘을 쉽게 이해할 것 같아서, 먼저 우선순위 큐를 간략하게 소개하겠다. 

 

1. 우선순위 큐 (Priority Queue)

우선순위 큐는 자료구조의 일종으로, 들어간 순서에 상관없이 우선순위가 높은것을 먼저 반환하는 자료구조이다. 

 

참고로 큐(Queue)는 First-In, First-Out(FIFO), 먼저 들어온것을 먼저 반환하는 자료 구조이며,

 

스택(Stack)은 Last-In, First-Out(LIFO), 가장 늦게 들어온것을 먼저 반환하는 자료구조이다. 

 

자세한 내용은 위키피디아를 참고하길 바라며, 본 포스팅에서는 우선순위 큐를 파이썬으로 구현하는 방법에 집중 할 것이다. 

 

파이썬에서 우선순위 큐는 heapq라는 모듈, 즉 힙(heap)을 사용해서 구현할 수 있다.  먼저 간단한 예제를 살펴보자.

import heapq    
heap = []   # heap이라는 리스트를 정의
heapq.heappush(heap, 2)    # heappush()라는 함수는 힙에 원소를 추가하는 함수임. heappush()를 통해
                                                #  리스트에 원소를 추가하는 순간 리스트는 최소 힙이 됨.
heapq.heappush(heap, 7)    # heap에 7을 추가
heapq.heappush(heap, 1)    # heap에 1을 추가
heapq.heappush(heap, 8)
print(heap)

 

코드 실행 결과

[1, 7, 2, 8]    # 입력은 2, 7, 1, 8 순서로 했지만, 출력은 최소값인 1이 가장 앞에 나오게 정렬됨.

 

 

코드 실행 결과를 살펴보면, 힙에 입력한 순서와 상관없이 입력했을때 가장 작은 원소가 힙의 가장 앞쪽에 나오는 것을 알 수 있을 것이다. 

 

우선순위 큐와 힙과 같은 자료구조에 대한 자세한 내용은 본 포스팅에서 생략하고, 여기서 핵심은 파이썬의 heapq라는 모듈을 통해서 

 

가장 작은 원소를 별도의 정렬 알고리즘을 사용하지 않고 최우선으로 출력할 수 있다는 것을 아는 것이 중요하다. 

 

다음 몇가지 예제를 통해 heapq모듈의 사용방법을 알아보도록 하자.

 

test = [3,1,7,2,8]     # test라는 리스트를 정의
heapq.heapify(test)   # test의 자료구조를 heap으로 전환
print(test)  # test 리스트가 힙으로 바뀌면서 가장 작은 원소인 1이 가장 좌측으로 정렬됨.

print(heapq.heappop(test))  # test 힙에서 가장 작은 원소를 pop시킴. 그럼 가장 작은 1이 test힙에서 튀어나옴.
print(test)  # test힙에서 1이 빠져나갔으며, 1을 뺀 이후 가장 작은 원소인 2가 가장 좌측에 있는 힙으로 바뀜.

print(heapq.heappop(test))  # test힙에서 현재 가장 작은 원소인 2를 pop시킴. 
print(test)  # test힙에서 2가 빠져나갔으며, 2를 뺀 이후 가장 작은 원소인 3이 가장 좌측에 있는 힙으로 바뀜.

 

코드 실행 결과

[1, 2, 7, 3, 8]
1
[2, 3, 7, 8]
2
[3, 8, 7]

 

 

위 예제에서처럼 힙에서 가장 작은 원소를 빼내면, 자동적으로 남아있는 원소들을 정렬하는 것을 알 수 있다. 

 

파이썬에서 제공하는 힙은 기본적으로 가장 작은 원소를 최 우선으로 하는 최소힙으로 설정되어 있다. 하지만 경우에 따라서는

 

숫자가 큰것이 우선시 되는 최대 힙이 필요할 수 있다.  그러한 경우 아래 코드를 참고하길 바란다. 

 

def max_heap(nums):
       heap = []
       max_heap_list = []
       for num in nums:
             heapq.heappush(heap, (-num, num))

       for i in range(len(heap)):
            max_heap_list.append(heapq.heappop(heap)[1])

       return max_heap_list

new_nums = max_heap(nums) 
print('최대힙으로 정렬 : ', new_nums)
print('가장 큰 값을 Pop : ' , heapq.heappop(new_nums))
print('남아있는 숫자들을 다시 최대힙으로 정렬 : ', max_heap(new_nums))

 

코드 실행 결과

최대힙으로 정렬 : [8, 7, 5, 4, 3, 1]
가장 큰 값을 Pop : 8
남아있는 숫자들을 다시 최대힙으로 정렬 : [7, 5, 4, 3, 1]

 

 

2. 다익스트라 알고리즘(dijkstra algorithm)

다익스트라 알고리즘은 일반적으로 그래프에서 두개의 노드의 최단경로를 찾을때 사용되는 알고리즘이다.  

 

다만 다익스트라 알고리즘을 사용하기 위해서는, 그래프의 arc의 가중치가 음이 아니여야 한다.  

 

일반적으로 Transportation network는 그래프의 arc가 거리(distance)를 의미하며 이는 양의 가중치를 가지고 있다는 것을 의미하기

 

때문에, 도로 교통망같은곳에서 최단경로를 찾을때는 다익스트라 알고리즘을 많이 사용한다. 

 

다익스트라 알고리즘의 의사코드는 위키피디아에 잘 정리가 되어 있으며, 아래의 파이썬 코드는 그를 바탕으로 작성되었다. 

 

# Input data
data = {'a': {'b' : 2, 'c' : 4},
             'b': {'a' : 2, 'c' : 3, 'd' : 8},
             'c': {'a' : 4, 'b' : 3, 'e' : 5, 'd' : 2},
             'd': {'b' : 8, 'c' : 2, 'e' : 11, 'f' : 22},
             'e': {'c' : 5, 'd' : 11,'f' : 1},
             'f': {'d' : 22, 'e' : 1} }

test = {'a': {'b': 2, 'c': 9223372036854775807},
            'b': {'a': 2, 'c': 3, 'd': 8},
            'c': {'a': 9223372036854775807, 'b': 3, 'e': 9223372036854775807, 'd': 2},
            'd': {'b': 8, 'c': 2, 'e': 11, 'f': 22},
            'e': {'c': 9223372036854775807, 'd': 11, 'f': 9223372036854775807},
            'f': {'d': 22, 'e': 9223372036854775807} }

#dijkstra algorithm
import heapq
import sys
import copy
def dijkstra(graph, src, dest):
       inf = sys.maxsize      # 각 노드별 cost를 infinity로 설정하기 위해 inf를 정의
       node_data = { }
     
 #initialization
       for i in graph:
            node_data[i] = {'cost' : inf, 'pred' : []}
       
      Q = list(node_data.keys())
      node_data[src]['cost'] = 0  # Define distance from source to source

      while True :
            min_heap = []
            for i in node_data :
                  if i in Q:  # 방문하지 않은 노드들을 대상으로 현재의 Cost를 힙에 저장
                       heapq.heappush(min_heap, (node_data[i]['cost'],i))
                  temp = min_heap[0][1] # 현재를 기준으로 Cost가 가장 적은 포인트를 temp에 저장
                  Q.remove(temp)  # temp를 제거하여, 반복문에서 방문했던 노드를 가지 않도록 함.
                  for j in graph[temp]:
                       cost = node_data[temp]['cost'] + graph[temp][j]
                       if cost < node_data[j]['cost']:
                             node_data[j]['cost'] = cost
                             node_data[j]['pred'] = node_data[temp]['pred']+list(temp)
                       
                       if Q == []:   # 모든 노드들을 방문하면 반복문을 종료하기 위한 조건문
                             break
     return (node_data[dest]['cost'], node_data[dest]['pred']+list(dest))  

dijkstra(data, 'b', 'e')

 

코드 실행 결과

(8, ['b', 'c', 'e'])  # 'data'그래프에서 'b'와 'e'의 최단경로의 거리(비용)은  8이며, 그때 경로는 b-c-e임을 의미함.

 

사실 다익스트라 알고리즘은 파이썬에서 이를 구현하는 모듈이 존재한다.

 

따라서 굳이 이를 사용자가 직접 구현할 필요는 없으나,

 

차후에 다익스트라 알고리즘을 활용한 다른 하이브리드 알고리즘을 개발할 때를 대비하여, 읽는이들이 한번쯤 직접 구현할 필요가 있을 것

 

같아서 이렇게 포스팅을 작성해봤다.