computer networking a top down approach ch5,7 일부
- 최초 등록일
- 2022.06.20
- 최종 저작일
- 2022.05
- 18페이지/ 어도비 PDF
- 가격 10,000원
* 본 문서는 PDF문서형식으로 복사 및 편집이 불가합니다.
소개글
"computer networking a top down approach ch5,7 일부"에 대한 내용입니다.
목차
1. CHAPTER 5: NETWORK LAYER: CONTROL PLANE
1) Dijkstra's Link State Algorithm (similar to Chapter 5, P3-5)
2) Dijkstra's Link State Algorithm - Advanced
3) Bellman Ford Distance Vector algorithm (similar to Chapter 5, P8)
2. CHAPTER 7: WIRELESS AND MOBILE NETWORKS
1) CDMA - Basic
2) CDMA - Advanced
3) 4G Wireless Tunneling
4) 4G Wireless Handover
본문내용
벨만-포드 알고리즘(Bellman-Ford Algorithm)이란?
• 벨만-포드 알고리즘은 한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘이다.
• 간선의 가중치가 음수일 때도 최단 거리를 구할 수 있다.
우리가 알고있는 다익스트라 알고리즘도 최단 거리를 구하는 알고리즘인데, '벨만-포드는 또 뭘까?'라는 생각이 들 수 있다. 다익스트라와 벨만-포드의 차이점에 대해 알아보자.
벨만-포드 vs 다익스트라
위 그림을 보자. 우리는 '1 번 노드에서 3 번 노드로 가는 최단 거리'를 구한다고 가정하자. 우리의 육안으로 보면 '1 번 -> 3 번'으로 가는 경로는 2 가지이다. 1 번 -> 3 번(cost:10)과 1 번 -> 2 번 -> 3 번(cost:2015=5) 2 가지로, '1 번 노드에서 3 번 노드로 가는 최단 거리'는 5 이다.
이제 육안으로 보지않고 다익스트라 알고리즘을 사용하게 되면 매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하므로 1 번 -> 3 번(cost:10)의 경로를 선택하게 된다. 이처럼 음수 간선이 존재하면 최단 거리를 찾을 수 없는 상황이 발생한다. 반면에 벨만-포드 알고리즘을 사용하게 되면 매번 모든 간선을 전부 확인하므로 1 번 -> 2 번 -> 3 번(cost:20-15=5)의 경로를 선택하여, 최단 거리를 찾을 수 있게 된다.
정리하자면,
[다익스트라 알고리즘]
• 매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하여 한 단계씩 최단 거리를 구해나간다.
• 음수 간선이 없다면 최적의 해를 찾을 수 있다. (음수 간선이 있을 때는 최적의 해를 찾을 수 X)
• 시간 복잡도가 빠르다. (OElogV) --> 개선된 다익스트라 알고리즘 (우선순위 큐 사용)
참고 자료
없음