[자료구조]Bellman-ford Algorithm 조사

소개글

자료구조

목차

1. Shortest Path length determination

2. Bellman-ford Algorithm

본문내용

1. Shortest Path length determination
가장 짧은 경로 스패닝 트리를 찾기 위해 경로상의 홉(hop) 수에 따라 반복하여 실행되는 라우팅 알고리즘이다. 거리벡터 라우팅 알고리즘(distance vector routing algorithm)이라고 한다. 이 알고리즘은 Smallest Hopping Account(Routing Table 정보)를 가지고 수시로 환경 정보를 자동 교환하는데,각 라우터가 인접한 라우터에게 망의 모든 라우터까지의 연결 비용을 알려준다.
이러한 가장 짧은 경로를 찾아주는 알고리즘으로는 두가지가 있는데 하나는 Bellman-Ford 알고리즘이고 그리고 또 하나는 Dijkstra’s 알고리즘이다.
2. Bellman-ford Algorithm
각 노드는 자신으로부터 데이터전송이 가능한 목적지 노드까지의 distance값을 인접한 노드의 distance vector값을 이용하여 반복적으로 수정하여, 최단 경로를 구하는 backward search algorithm이다
위의 그림들은 Bellman-Ford 알고리즘을 설명한 그림이다. 라우팅 테이블의 값을 결정하는 방식인데, 첫번째 그림의 오른쪽 그림에 보면 목적지에 바로 연결되어 있는 경우는 0으로 설정되게 된다.두번째 단계에서 보면 다른 값들이 결정되는데 위쪽의 Min(5+0, 2+2)의 경우와 같이 경로가 두가지 이상일 경우는 적은 값을 취하여 갖게 된다. 그렇게 된 다음 다음 단계의 값들도 오른쪽 그림과 같이 결정된다.

참고 자료

없음