# 힙(heap)과 다익스트라(dijkstra) 알고리즘

다익스트라 알고리즘을 구현하기 위해 반드시 힙이 필요하지는 않다. 다만, 공부한 교재 ‘Inroduction to Algorithms’에서는 최소 우선 순위 큐를 이용하기 때문에 힙을 사용하였을 뿐이다. ※ 힙(heap) 힙은 이진 트리 기반이지만, 값이 입력될 때 정렬이 된다는 점이 이진 트리와 큰 차이점이다. 즉, 최소값 혹은 최대값을 출력할 때 트리나 다른 자료 구조에서는 정렬이나 탐색 과정을 거쳐야 하는 반면, 힙은 그런 과정이 생략되고 루트 노드만 반환한다면 원하는 값을 얻을 수 있다. 따라서 힙은 다른 자료 구조에서는 수행하지 않는 ‘heapify’라는 작업을 수행하여 루트 노드에 최소값 혹은 최대값을 유지한다. 아래는 교재에서 소개된 최대값에 대한 heapify를 수행하는 알고리즘을 최소값에 대한 heapify로 수정한 알고리즘이다. Min-HEAPIFY(A, i) l ← LEFT(i) r ← RIGHT(i) if l ≤ heap-size[A] and A[l] < A[i ] then shortest ←l else shortest ←i if r ≤ heap-size[A] and A[r] < A[shortest] then shortest ←r if shortest = i then exchange A[i ] ↔ A[shortest] Min-HEAPIFY(A, shortest) 이 heapify과정만 제대로 이해해서 적기적시에 사용할 줄만 안다면 힙과 힙을 이용한 정렬에 관한 내용은 제대로 이해했다고 보면 된다. 실제로 구현 상 오류는 이 heapify과정이 제대로 수행되지 않아 발생하는 경우가 대부분이었다. ※ 우선 순위(priority queue)에 기반한 자료구조 자료구조를 구성하는 각 원소(element)는 우선 순위를 가질 수 있다. 다시 말해, 상대적으로 우선 순위가 높거나 낮은 원소가 가장 먼저 혹은 가장 늦게 처리될 수 있다. 예를 들어, 우리가 다이어리에 일정을 적고 그 일정에 우선 순위를 매겨 먼저 처리해야 할 일과 늦게 처리해야 할 일을 분류하는 것이라고 보면 된다. 우선 순위를 부여한 자료구조는 무엇으로든 만들 수 있다. 큐(queue), 스택(stack) 등등 자료 구조를 이루는 모든 원소에 우선 순위를 부여하고 이 우선 순위에 따라 자료 구조의 원소를 순서대로 처리한다면 그 자료는 우선 순위에 기반한다고 보면 된다. 이 때, 동일한 우선 순위를 가진 원소들에 대해서 우선 순위는 무의미하기 때문에 이 때는 자료 구조의 정책에 따라서 원소를 처리한다. 큐의 경우에는 ‘선입선출’, 스택의 경우에는 ‘후입선출’의 방식으로 원소를 처리한다. ※ 다익스트라(dijkstra) 알고리즘 다익스트라 알고리즘은 시작점에서 각 꼭지점에 이르는 가중치(혹은 거리)의 합의 최소를 구하는 것이다. 그래프에 제시된 노드 간의 가중치를 요리조리 더해보며 최소의 합을 구해보면 되지만, 언제나 그렇듯 간단한 원리조차도 프로그래밍 하려면 신중에 신중을 기해야 하는 법이다. 교재에서 제시된 다익스트라 알고리즘은 힙을 기반으로 하는 최소 우선 순위 큐를 사용하며, 큐의 변화를 관찰하며 원리를 파악해야지만 알고리즘을 제대로 이해할 수 있다.  아래는 교재에서 예시로 제시된 그래프이다. 이 그래프에서 흰색의 노드는 현재 큐(Q)에 존재하고, 검정색의 노드는 현재 S(Solution)에 존재한다. 그리고 회색의 노드는 큐의 원소 중 가장 최소의 가중치를 가진 노드이다. 즉, (a)에서 제시된 그래프가 입력으로 제시된 최초의 그래프이며, (f)에서 검게 색칠된 노드에 적힌 숫자들이 출력되어야 하는 결과이다. 또한, (a)~(f) 과정 동안 회색 노드가 선택되면서 결과를 구하는 과정이 진행되며, (a)에서 보듯, 출발점은 가장 왼쪽의 s가 적힌 노드이다. 최단 경로를 찾는 알고리즘에서는 아래의 ‘Relaxation’ 알고리즘이 제시된다. 아래의 알고리즘에서 u는 최소 가중치를 가진 노드의 번호이고, v는 u에 인접하는 어떤 노드의 번호이며, w는 u→v로 향하는 간선의 가중치이다. 이 알고리즘은 v로 향할 수 있는 최소의 가중치를 업데이트하며, 또한, 현재의 경로를 기록하여 ‘히스토리(history)’를 남긴다. RELAX(u, v, w) if d[v] > d[u] + w(u, v) then d[v] ← d[u] + w(u, v)   π[v]← u (정말 별것 없는 알고리즘 같아 보이지만, 막상 이 알고리즘이 제시되지 않는다면, 프로그래밍에 꽤 애를 먹을 것이다.) 위의 알고리즘까지 이해되었다면 다익스트라 알고리즘을 구현할 수 있다. DIJKSTRA(G, w, s) INITIALIZE(G, s) S ← ∅ Q ← V[G] while Q = ∅ do u ← EXTRACT_MIN(Q) S ← S ∪{ u } for each vertex v ∈ Adj[u] do RELAX(u, v, w) 먼저 INITIALIZE 단계에서 그래프를 등록하고, 출발점을 설정해야 하며, 최단 경로를 구하는데 사용할 자료구조 S와 최소 우선순위 큐를 초기화한다. 이후에는 큐가 빌 때까지 반복문을 수행하면서, 큐의 루트 노드를 EXTRACT하여 현재 노드 u를 업데이트하고, S를 업데이트 하면서 인접 노드에 대한 가중치를 구하는 과정을 반복한다. (참 간단한 알고리즘이건만, 이것조차도 원리와 개념을 제대로 파악하지 못하면 이해하고 구현하는 데 상당한 시간이 걸린다.) 참고 자료 Thomas H. Cormen, 『Introduction to Algorithms』