- 다익스트라, 벨만-포드 알고리즘으로 최소 비용 구하기 -
문제는 위 그래프를 바탕으로 최소 비용을 구하는 것이다. 첫번째 방법은 다익스트라 알고리즘을 사용하는 것이고 두번째는 벨만-포트 알고리즘을 사용하는 것이다. 시작은 2번 노드에서 한다.
시작을 1번 노드에서 한다면 아래 표와 같을 것이다.
다익스트라 알고리즘 : k번째 단계에서는 발신지 노드에서 가장 적은 비용을 가진 k개의 노드들이 최단 경로로 결정된다. 이 노드들은 집합 T에 있다. 다음 단계에서는 T에 없는 노드 중 발신지 노드로부터 가정 적은 비용의 노드를 T에 추가한다. 노드가 6개이므로 6번 반복한다.
벨만-포드 알고리즘 : 발신지 노드로부터 많아야 하나의 링크를 갖는 최소 비용을 찾고 그 다음은 링크가 2개인 최소 비용을 찾아야 한다.
다익스트라 알고리즘(s=2) 최소 비용 계산
반복 T | L(1) 경로 | L(3) 경로 | L(4) 경로 | L(5) 경로 | L(6) 경로 |
1 {2} | 3 2-1 | 3 2-3 | 2 2-4 | ∞ - | ∞ - |
2 {2,4} | 3 2-1 | 3 2-3 | 2 2-4 | 3 2-4-5 | ∞ - |
3 {1,2,4} | 3 2-1 | 3 2-3 | 2 2-4 | 3 2-4-5 | ∞ - |
4 {1,2,3,4} | 3 2-1 | 3 2-3 | 2 2-4 | 3 2-4-5 | ∞ - |
5 {1,2,3,4,5} | 3 2-1 | 3 2-3 | 2 2-4 | 3 2-4-5 | 5 2-4-5-6 |
6 {1,2,3,4,5,6} | 3 2-1 | 3 2-3 | 2 2-4 | 3 2-4-5 | 5 2-4-5-6 |
반복이 계속 되면서 집합 T에 시작 노드로부터 최소비용을 갖는 노드가 추가 되는 것을 볼 수 있다. L은 Lowest의 약자 같다. 최소 비용이라는 의미이다. 경로는 시작 노드가 2 이므로 2부터 시작해서 최소 비용을 갖는 노드를 거치게 된다.
벨만-포드 알고리즘(s=2) 최소 비용 계산
h | L(1) 경로 | L(3) 경로 | L(4) 경로 | L(5) 경로 | L(6) 경로 |
0 | ∞ - | ∞ - | ∞ - | ∞ - | ∞ - |
1 | 3 2-1 | 3 2-3 | 2 2-4 | ∞ - | ∞ - |
2 | 3 2-1 | 3 2-3 | 2 2-4 | 3 2-4-5 | 8 2-3-6 |
3 | 3 2-1 | 3 2-3 | 2 2-4 | 3 2-4-5 | 5 2-4-5-6 |
4 | 3 2-1 | 3 2-3 | 2 2-4 | 3 2-4-5 | 5 2-4-5-6 |
h는 최대 링크 수 이다. 링크는 노드와 노드를 연결해주는 선을 말한다. 일단 h가 0인 경우 아무 노드에도 연결될 수 없기 대문에 비용은 무한대이고 경로는 없다. h가 1이 되면 노드 2에서 하나의 링크만으로 도달할 수 있는 노드를 찾는다. 노드 5와 노드 6은 링크 하나로 도달할 수 없기 때문에 최소 비용은 무한대이고 경로도 없다. h가 2인 시점 즉 노드 2로부터 링크가 2개 연결될 수 있는 시점에선 노드 5와 6의 최소 비용이 결정된다. 이후 링크의 수가 늘어나면 더 적은 비용으로 우회하여 노드 6에 도달할 수 있다.
'과목 > 컴퓨터 네트워크' 카테고리의 다른 글
| 네트워크 모델 (0) | 2019.08.23 |
|---|---|
| 인터넷 기초 지식 (0) | 2019.08.23 |
| OSI 7 Layer (0) | 2019.07.23 |
| 쿠키와 세션 그리고 OAuth (0) | 2019.07.20 |
| 17장 무선 전송 기법 - Barker Sequence (0) | 2017.10.25 |
