벨만 포드 알고리즘은 한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘이다.
간선의 가중치가 음수일 때도 최단 거리를 구할 수 있다.
다익스트라 알고리즘도 최단 거리를 구하는 알고리즘인데. 벨만 포드는 또 뭘까? 라는 생각이 들 수 있다. 다익스트라와 벨만 포드의 차이점에 대해서 알아보자
위 그림을 보자 1번 노드에서 3번 노드로 가는 최단 거리를 구한다라고 가정하자. 우리의 육안으로 보면 1 -> 3으로 가는 경로는 2가지 이다.
1 -> 3 cost 10 , 1 -> 2 -> 3 cost 5 2가지로 1번 노드에서 3번 노드로 가는 최단 거리는 5다.
이제 육안으로 보지 않고 다익스트라 알고리즘을 사용하게 되면 매번 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택하므로 1번 -> 3번 cost : 10의 경로를 선택하게 된다. 이처럼 음수 간선이 존재하면 최단 거리를 찾을 수 없는 상황이 발생한다.
반면에 벨만 포드 알고리즘을 사용하게 되면 매번 모든 간선을 전부 확인하므로 1 -> 2 -> 3 cost 5 의 경로를 선택하여 최단거리를 찾을 수 있게된다.
- 매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하여 한 단계씩 최단 거리를 구해나간다.
- 음수 간선이 없다면 최적의 해를 찾을 수 있다.
- 시간 복잡도가 빠르다
O(ElogV)
- (정점 1)번의 매 단계마다 모든 간선을 전부 확인하면서 모든 노드간의 최단거리를 구해나간다. 다익스트라와의 차이점은 매 반복마다 모든 간선을 확인한다는 것이다. (다 익스트라는 방문하지 않은 노드 중에서 최단 거리가 가장 가까운 노드만을 방문)
- 다익스트라 알고리즘에서의 최적의 해를 항상 포함하게 한다.
- 음수 간선이 있어도 최적의 해를 찾을 수 있다.
- 시간 복잡도가 느리다
O(VE)
모든 간선의 비용이 양수일때는 다익스트라, 음수 간선이 포함되어있으면 벨만포드를 사용하면 된다.
- 출발 노드를 설정한다.
- 최단 거리 테이블을 초기화한다.
- 다음 과정을 (V - 1)번 반복한다.
- 모든 간선 E개를 하나씩 확인한다.
- 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
- 만약 음수 간선 순환이 발생하는지 체크하고 싶다면 3번 과정을 한 번 더 수행한다. -> 이때 최단 거리 테이블이 갱신된다면 음수 간선 순환이 존재하는 것이다.