Dijkstra Algorithm

다익스트라 알고리즘은 가중치를 가지는 양방향 그래프에서 특정 정점에 대한 나머지 정점들로의 최단거리를 구하는 알고리즘이다.
가중치를 가지는 간선을 가지는 그래프를 G[V,E] 라하고 정점들의 집합을 S, Q두개로 가질 수 있다고 할때 알고리즘은 아래와 같이 기술될 수 있다.

while Q is not empty
 S = empty
 Q = G[V,E]
 u = extract_min(Q);
 for edge from u
   relax(edge, u)

간단히 기술하면, 먼저 시작점 s 로부터 걸리는 경로 값을 각 정점에 기록할 수 있다고 할때, 모든 정점에 infinite 값 (아주 큰값)을 넣은 후 모든 정점들을 Q에 넣는다(s 에는 값 0을 넣는다). 그리고 Q 에서 최소 값을 가지는 정점을 하나 꺼내어 이 정점이 가지는 모든 간선들에 대해 relax를 수행한다. relax 란 간선들과 연결된 정점들에 최단 경로값을 갱신해 넣어주는 것을 말한다(이미 Q에서 빠져나온 노드들에 대해서도 갱신한다). 이 과정을 Q에 정점이 없을 때까지 반복한다.