[컴퓨터 통신망] - 최소 비용 알고리즘 정리

소개글

최소 비용 알고리즘을 좀 더 이해하기 쉽게 정리하여 설명

목차

10A 최소 비용 알고리즘: Least-cost (routing) algorithm

1. 초기화.
2. M에 포함되어 있지 않은 node 중에서 node S로부터 최소비용을 갖는 node가 M에 더해진다.
3. 최저비용경로를 갱신(update)한다.

예제: 그림 12.2.

본문내용

1. 초기화.
set M={s}
= for : source에서 이웃 nodes ( neighboring nodes )까지의 초기 경로비용 ( 초기경로비용 = link 비용 )

설명: = 현재 algorithm 이 알고 있는 source S 로부터 node n 까지의 최저비용경로의 비용이라고 했으니까 처음에는 직접가는 비용이 최소가 된다.

2. M에 포함되어 있지 않은 node 중에서 node S로부터 최소비용을 갖는 node가 M에 더해진다.
Find such that
and Add w to M

3. 최저비용경로를 갱신(update)한다.


이 minimum이면, S에서 n으로 가는 최소비용경로는
S에서 w를 거쳐가는 경로에 w에서 n을 거쳐가는 경로를 연결한 것이 된다.

참고 자료

없음