Dijkstra Algorithm

Dijkstra Algorithm

1. 집합 S를 정의하여 공집합으로 초기화한다. 

2. 그래프의 각 정점 u에 대해 d(u)가 정의되어, u=s인 경우 0으로, 나머지 경우 ∞​으로 초기화한다.
  즉, d(s) := 0, d(v) := ∞​ (v≠​​s)​3. S에 속해있지 않은 V의 원소에서 d(u)의 값이 최소가 되는 정점 u를 선택하여 S에 추가한다.  

4. u와 연결된 모든 정점을 v1, ..., vk라 두자. 
  기존의 d(vi)​ (i=1, 2, ... , k)​ 값보다​ d(u)+w(u, vi)​ 의 값이 더 작다면, d(vi)​​의 값을 d(u)+w(u, vi)로 수정해준다.
  즉, ​d(vi)​ := ​min{d(vi), ​d(u)+w(u, vi)} ​(i=1, 2, ... , k) 

5. S와 V가 일치할 때까지 3번과 4번을​ 반복해준다.
  최종적으로 얻어지는 d(u)의 값이 s에서 임의의 정점 u까지의 최단 경로의 길이이다.

Uk는 k번째 단계에서 선택된 정점
Sk는 k번째 단계에서 집합S
Dk(v)는k번째 단계에서의 d(v)로 정의된다.
D(v,v')은 v에서 v'을 잇는 최단경로이다.

Reference)
http://m.blog.naver.com/sehoon95/220115473322