벨만포드와 다익스트라 알고리즘

DV와 Link State를 공부하다가 위의 둘 알고리즘에 대해 복습을 한다. 필자의 기억에 의하면 자료구조 6장 그래프에 나왔던 것으로 기억한다.

가장 큰 차이점은 다익스트라는 음의 가중치를 가질 수 없고 벨만포드는 음의 가중치를 가질 수 있다.

다음 그림으로 위의 알고리즘을 간단히 설명한다.

위의 그림에서 B의 위치에서 다익스트라 알고리즘은 D로 갈려면 D로 바로가면 20 C를 거치게 되면 40+알파인데 현재 가중치의 값으로 결정을 해서 B->D를 선택하게 된다.

하지만 벨만포드는 음의 가중치를 가질 수 있기 때문에 끝가지 돌아보고 나서 B->C->D를 선택하게 된다.