computer networking a top down approach ch5,7 일부

소개글

"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) --> 개선된 다익스트라 알고리즘 (우선순위 큐 사용)

참고 자료

없음