본문내용
ex]
소스 S로부터 최소의 Cost를 가진 T에 없는 이웃한 지점들을 찾는다. 이 과정을 표현하면 다음과 같이 쓰여질 수 있다.
Find such that L(x) =
이렇게 찾은 x를 T에 추가한다.
3. [Update least-cost paths]
L(n)=min[L(n), L(x) + w(x,n)] for all n I M
만약 나중 텀이 최소라면, s에서 n까지의 경로는 s에서 x까지의 경로이다.
이 알고리즘은 모든 지점들이 T에 추가될 때 끝나게 된다. 그리고 각 지점 x 와 연관된 L(x)값은 소스 s로부터 목적지 n까지 가는 최소 Cost 경로이다. 덧 붙여 말하자면 T는 어떤 Spanning Tree이고 s로부터 각 지점까지 가는 경로에서 최소값을 가지는 경로를 정의해 놓은 것이다.
소스 S로부터 최소의 Cost를 가진 T에 없는 이웃한 지점들을 찾는다. 이 과정을 표현하면 다음과 같이 쓰여질 수 있다.
Find such that L(x) =
이렇게 찾은 x를 T에 추가한다.
3. [Update least-cost paths]
L(n)=min[L(n), L(x) + w(x,n)] for all n I M
만약 나중 텀이 최소라면, s에서 n까지의 경로는 s에서 x까지의 경로이다.
이 알고리즘은 모든 지점들이 T에 추가될 때 끝나게 된다. 그리고 각 지점 x 와 연관된 L(x)값은 소스 s로부터 목적지 n까지 가는 최소 Cost 경로이다. 덧 붙여 말하자면 T는 어떤 Spanning Tree이고 s로부터 각 지점까지 가는 경로에서 최소값을 가지는 경로를 정의해 놓은 것이다.