- Shortest Path 문제를 풀기 위한 알고리즘
* 구조
1. 모든 node의 dmin값을 V0부터 자신까지의 weight로 한다.
2. V0를 T에 넣고, T에 없는 node중 dmin값이 가장 작은 node를 u라 하고, u를 T에 추가.
3. T에 없는 모든 node의 dmin 값을 기존 값과 dmin(u) + g(u,w) 중에서 더 작은 값으로 보정.
4. T의 개수가 n이 될 때까지 2,3을 반복.
* 증명
- 알고리즘이 SP문제를 정확히 풀어내는지 증명.
1. u가 T에 포함되어 있으면 dmin(u)는 global SP. ( = d(u) )
2. u가 T에 포함되어 있지 않으면 dmin(u)는 dt(u) ( T에 있는 node만 사용했을 때의 S.P)
1,2를 증명하기 위해, 수학적 귀납법 사용
base) 최초에 V0만 T에 포함되어 있을때, 1,2는 모두 성립한다.
step) T의 개수가 k 일 때 증명이 성립한다고 가정하자. 그리고 알고리즘이 T에 u를 추가하여 T'이 되었다고 하자.
- 추가되기 전의 dmin(u) = dt(u) 이다. ( 알고리즘이 dt가 아닌 dmin값을 설정하는 일이 없다.)
- dmin(u) = d(u) 이다. 즉, V0에서 u까지의 SP는 현재 T에 있는 node들 만으로 이루어져 있다.
-> 그렇지 않다면, V0와 u사이에 v라는 node가 존재한다. v는 T에 포함되지 않는 node이다.
d(u)는 dt(u)보다 작다. 그리고 dt(v)는 d(u)보다 작다.
-> dt(u)보다 작은 dt(v)가 존재한다. 이것은 모순이다. (알고리즘은 u를 추가했으므로)
따라서 알고리즘이 추가하는 u의 dmin(u)는 d(u)이다.
-> 1 성립.
- T'에 속하지 않는 node w를 고려해보자.
- 알고리즘이 u를 추가하기 직전의 dmin(w) = dt(w)이다. (수학적귀납법 step과정에서 가정한 사실)
u를 추가하고 나서는 dmin(w) = dt'(w)가 되어야 한다.
- dt'(w)는 dt(w)와 d(u) + g(u,w) 두 값중 하나로 보정된다.
1) dt'(w)가 dt(w)로 보정된다면, step에서 가정한 사실에 의해서 그대로 2가 성립한다.
2) dt'(w)가 d(u) + g(u,v)로 보정된다면, dmin(w) = dt(w)가 성립되기 위하여
V0에서 w까지의 SP에는 u가 포함되어 있어야 하며 특히 u는 w 바로 앞에 있어야 한다.
즉, u와 w 사이에는 node가 없어야 한다.
- 만약 u와 w사이에 x라는 node가 있다고 가정한다면,
x는 T에 포함된 node이고 ( x가 T에 포함되지 않는 node는 고려할 필요가 없다. 여기서는 dt(w)를 증명하면 되기 때문)
x의 SP는 u를 포함하지 않는다.(u는 이번 단계에서 추가된 node이기 때문)
- 2)에서 dt'(w)가 d(u) + g(u,v)로 보정되었으므로, w의 SP에는 u가 포함되어야 한다. 여기서 모순이 생겼다.
- 따라서 u와 w사이에는 다른 node가 없다.
- 그래서 2)의 경우에도 2가 성립한다.
모든 경우에 2가 성립하므로 step은 참이다.
따라서 알고리즘은 정확히 동작함을 증명하였다.
'학부 전공 > 알고리즘' 카테고리의 다른 글
| Selection (0) | 2010.10.29 |
|---|---|
| Tape에 데이터 담기 (0) | 2010.10.11 |
| Job Scheduling (0) | 2010.10.08 |
| Kruskal 알고리즘 (0) | 2010.10.08 |
| Prim 알고리즘 (0) | 2010.10.07 |