다익스트라

Dijkstra algorithm

다익스트라 알고리즘

알고리즘 개요

알고리즘 개요

데이크스트라 알고리즘은 각각의 꼭짓점 v에 대해 s에서 v까지의 최단 거리 d[v]를 저장하면서 작동한다. 알고리즘의 시작 시에 이 값은 s에 대해서는 0이고, (d[s]=0) 다른 모든 꼭짓점에 대해서는 무한대(∞) 값으로 놓아 다른 꼭짓점에 대해서는 아직 최단 경로를 모른다는 사실을 표시한다. 알고리즘이 종료되었을 때 d[v]는 s에서 v까지의 최단 경로의 거리를 나타내게 되고, 만약 경로가 존재하지 않으면 거리는 여전히 무한대로 남는다.

데이크스트라 알고리즘은 변 경감(edge relaxation)이라고 불리는 기본 연산을 바탕으로 한다. s에서 u까지의 최단 경로(d[u])를 이미 알고 있고, u에서 v까지의 변 (u, v)가 존재할 때, s에서 v까지의 최단 경로는 u까지의 최단 경로에 변 (u, v)를 연장함으로써 얻을 수 있다. 이 경로의 비용은 d[u]+w(u, v)가 되며, 이 비용이 현재의 d[v] 값보다 낮으면 d[v]를 새로운 값으로 바꾼다.

경감 연산은 모든 변 (u, v)에 대해 한번씩 경감이 적용되어 모든 d[v]가 최단 경로의 비용을 나타내게 되었을 때 끝난다.

알고리즘은 과정이 끝날 때까지 꼭짓점의 집합 S와 Q를 저장한다. S는 d[v]가 최단 경로의 비용임이 이미 알려진 꼭짓점 v의 집합이고 Q는 나머지 꼭짓점들의 집합을 가리킨다. S는 공집합에서 시작하여 매 단계마다 Q에서 S로 꼭짓점들이 하나씩 옮겨 오며, 이때 옮겨 오는 꼭짓점들은 d[u]가 가장 낮은 값을 갖는 꼭짓점 u로 정해진다. u가 S로 옮겨 오면, 알고리즘은 u에서 시작하는 모든 변에 대해 경감 연산을 행한다.

이를 이용하여 최단거리를 구할 수 있다. 아래는 위키피디아에서 가져온 관련 Gif 파일이다.

참고 

http://en.wikipedia.org/wiki/Dijkstra's_algorithm

http://ko.wikipedia.org/wiki/데이크스트라_알고리즘#.EC.9D.98.EC.82.AC.EC.BD.94.EB.93.9C