힙(Heap)을 이용한 다익스트라(Dijkstra) 알고리즘

다익스트라 알고리즘은 방향이 있는 가중치 그래프에서의 단일 시작점 최단 경로 알고리즘이다.
단, 조건으로 모든 간선의 가중치가 음이 아닌 수여야 한다.
다익스트라 알고리즘은 해 집합(S)에서 해가 아닌 집합(T)로 향하는 경로 중, 가장 짧은 경로를 매번 선택한다.
아래 그림을 보자. 단일 시작점을 a라 하고, 위에서 말한 정의에 따라 표현했다.

특정 시점에서의 가장 짧은 경로를 a→u-v라 하자. 즉, a에서 u까지 가는 경로에 간선 u-v를 추가하는 경로이다.
이 때, v가 S에 포함되는 경우가 2가지 경우가 있다.
1) a에서 S의 원소 u까지 가는 최단 경로에다가 u-v를 잇는 간선을 추가해서 v가 S의 원소가 되는 경우
2) a에서 T의 원소 u'까지 가는 최단 경로에다가 u-v를 잇는 간선을 추가해서 v가 S의 원소가 되는 경우
1)은 우리가 주장하는 알고리즘이기에, 2)의 경우가 발생하면 모순임을 보이려 한다.

가정에 의해 a→u-v의 경로의 길이가 a→u'의 경로의 길이보다 작거나 같다.
그리고 u'-v 간선의 길이 L은 길이가 0 이상이다.
2)의 경우가 발생하면 a에서 v에 이르는 경로가 최단 경로가 아니게 되므로 가정에 모순이다.

세부 알고리즘을 적어보면 아래와 같다.
1. 초기화
  dist(x)를 시작점 a에서 x에 이르는 최단 경로의 길이라 정의하자.
  힙(Heap)을 정의하는데 힙의 한 원소는 (경로의 길이, 경로의 끝점)으로 구성되며, 경로의 길이가 짧은 것이 부모가 될 조건으로 정의된다.
  dist(a) = 0, dist(x) = infinite(x≠a)으로 초기화한다.
  힙에 (0, a)을 삽입한다.
2. 힙이 비어있지 않을 동안 아래 동작들을 반복한다.
  S에서 T로 향하는 경로 중 최단 경로를 선택하여, T의 원소 하나를 S에 포함시킨다.
  힙에서 최상위 부모 원소를 하나 빼낸다. 그 원소를 (L, x)라 하자.
  만약 dist(x)보다 L이 더 크다면, 현재 원소는 고려할 필요가 없는 원소이므로 무시한다.
  그렇지 않다면, x에서 향하는 모든 정점들 y에 대해 L2 = L + (x-y 간선의 길이)와 dist(y)를 비교한다. dist(y)보다 L2가 더 작다면 dist(y)를 L2로 갱신하고, 힙에 (L2, y)를 삽입한다.

아래 코드는 다익스트라 알고리즘 예제 문제인 BOJ 1753번을 맞춘 것이다.