이전 포스팅에서 라우팅 관련 알고리즘을 간략히 다뤘었다.
global routing algorithm은 다익스트라를, 분산형 routing algorithm은 벨만포드를 사용한다고 얘기했다.
다익스트라는 평상시에 조금 접해본 알고리즘이지만 벨만포드는 익숙치 않아 이에 대해 자세히 정리하기 위하여 본 포스팅을 작성한다.
다익스트라
다익스트라 알고리즘은 weight가 양수인 그래프에서 특정 노드로부터 모든 노드로의 최단 거리를 구할 때 사용한다.
자세한건 다익스트라 알고리즘 포스팅을 참고하라!
벨만 포드
벨만 포드 알고리즘은 다익스트라 알고리즘과 목적이 똑같지만 weight가 음수여도 가능하다는 특징이 있다.
[s ➡️ v]의 최단 거리를 구하기 위해 [s ➡️ u]의 최단 거리에 [u ➡️ v]의 거리를 더한다. 이를 그림으로 표현하면 아래와 같다.
한계
벨만 포드는 음수 사이클이 존재할 때 무용지물이다.
예를 들어, 위 그림에서 [s-x-u] 삼각형이 음의 사이클을 이룬다고 가정해보자. 그러면 v로 가는 최단거리는 [s-x-u] 사이클을 무한히 돈 다음 v로 가는 것이 최단거리이기 때문이다.
Reference
0x68656C6C6F21