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

두 알고리즘의 가장 큰 차이점은, 다익스트라 알고리즘은 가중치가 음수인 경우는 처리 못하고, 벨만 포드 알고리즘은 가중치가 음수인 경우도 처리가능하다는 점이다.

다익스트라 알고리즘은 기본적으로 Greedy 탐색이므로, 비용이 감소하는, 이득이 되는 경우를 고려하지 못한다.

당장 비용이 최소라 생각하면, 그 길을 택한다.

하지만 경우에 따라서 멀리 돌아서 가는 경우가 오히려 비용이 적게 드는 경우가 있을 수 있다. 이런 경우까지 처리 가능한 알고리즘이 바로 벨만 포드 알고리즘이다.

다음과 같은 그래프에서 A에서 D로 가는 최단 경로를 찾는다고 하자

다익스트라 알고리즘의 경우 B에서 C와 D사이에서 고민하게 된다. 당장 D로 가는 경로가 가중치가 적기 때문에 B->D를 선택할 것이다.

하지만 가중치가 음수가 있을 수 있는 경우, 끝까지 돌아봐야 결과를 알 수 있다. 

음수가 없이 모두 양수만 가능한 경우는, 총 비용이 증가하는 방향으로만 있기 때문에 Greedy하게 탐색해도 좋은 결과를 얻는 것이다. 

이와 관련하여 Maximum sum 문제의 Kadane's algorithm을 생각해 볼 수 있다.

출처 : http://codeng.tistory.com/150