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

이번 글에서는 다익스트라 알고리즘과 벨만포드 알고리즘을 서로 한번 비교해보자.

먼저, 다익스트라와 벨만포드 알고리즘에 대한 개념은 이번글에서는 하지 않을 것이다.

각 알고리즘에 대한 설명은 아래에 있으니 아직 모른다면 읽고 오도록 하자.

[ 다익스트라 알고리즘 알아보기 ]

[ 벨만포드 알고리즘 알아보기 ]

1. 다익스트라 알고리즘과 벨만포드 알고리즘의 공통점

먼저 2개의 알고리즘 모두, 그래프 알고리즘에서 '최소비용'을 구할 때 사용되는 알고리즘이다.

또한 두 알고리즘 모두, "하나의 정점에서 다른 모든 정점으로의 최소비용" 만 구할 수 있다.

즉, 모든 정점들 간의 최소비용을 구할 수는 없다. 물론, 구하기 위에서 모든 정점에서 다익스트라 혹은 벨만포드 알고리즘을

실행한다면, 구할 수는 있지만, 일반적으로 한번만 실행했을 때, 그 결과는 "시작점으로 생각되는 하나의 정점에서 다른 모든 정점으로 갈 때 드는 최소비용" 만 구할 수 있다.

만약, 모든 정점간의 최소비용을 구하고 싶다면, '플로이드 워샬 알고리즘'을 사용하면 된다.

따로 플로이드 워샬 알고리즘에 대해서 다루지는 않았지만, 플로이드 워샬 알고리즘을 사용하면, 모든 정점간의 최소비용을

구할 수 있다.

2. 다익스트라 알고리즘과 벨만포드 알고리즘의 차이점

먼저, 다익스트라 알고리즘은 "음의 가중치가 없는 그래프일 때만 사용이 가능" 하다.

지금 당장 눈 앞에 직접 연결된 정점들 중, 가장 비용이 적게 드는 정점을 선택하는 그리디한 방식으로 진행되는 다익스트라

특징 상, 음의 가중치가 있게 되면 이 규칙이 완전히 깨져버리게 된다.

따라서 다익스트라 알고리즘은 "음의 가중치가 없는 그래프일 때, 최소비용을 구하는 알고리즘" 이다.

반대로 벨만포드 알고리즘의 경우, 음의 가중치가 있어도 사용이 가능하다.

벨만포드 알고리즘에 대한 설명을 쓴 글에서도 말했듯이, 벨만포드 알고리즘의 경우, 탐색을 하면 할 수록 특정 정점으로 가는

비용이 한 없이 작아지는 '음의 사이클' 을 찾아낼 수 있다.

따라서, 그래프에 음의 가중치가 있다면, 벨만포드 알고리즘으로 최소비용을 구할 수도 있고, 그럴 수 없다면, '음의 사이클'이 존재하는지 파악할 수 있다.