벨만 포드 알고리즘

그래프 최단 거리 알고리즘

벨만 포드 알고리즘은 그래프 최단 거리를 구하는 알고리즘 중 하나이다.

대표적으로 다익스트라 알고리즘은 모든 간선의 가중치가 양수일 때만 가능하다.

다익스트라

다익스트라가 어떻게 동작하는지 간단하게 살펴보자.

이런 그래프가 있다고 가정한다.

 

A에서 E까지의 최단거리를 구할 것이다.

A에서 가능한 경로 중 가장 빠른 경로를 선택하여 이동할 것이다.

 

A에서 B로 가는 경로가 선택되어 A에서 B까지의 경로는 최단 거리가 3인 것을 알 수 있다.

이후 B에서 갈 수 있는 경로를 큐에 넣고 다시 탐색을 반복할 것이다.

 

이렇게 각 최단거리를 구하다 보면 E까지의 최단거리가 11이라는 것을 알 수 있다.

그런데 이 방법은 모든 가중치가 양수일 때만 가능하다. 그림처럼 D에서 B로 가는 경로는 -100이기 때문에 A에서 B로 가는 최단 경로는 3이 아닌 -92가 된다.

 

벨만 포드 알고리즘

벨만 포드 알고리즘은 이러한 음수 가중치가 있는 경우에 최단 거리를 구할 수 있는 방법이다.

구하는 방법은

 

1. 모든 최단 거리를 최댓값으로 초기화 한다. (출발지에서 B까지의 최단 거리는 INF, C까지는 INF ... )

2. 모든 간선을 확인하며 최단 거리를 업데이트 한다.

3. 2번을 N-1번 반복한다. (N은 노드의 개수)

 

벨만 포드 알고리즘에서는 음수 순환 사이클이 존재하는지도 확인할 수 있는데 이건 뒤에서 살펴보자.

 

출발지인 A를 제외한 나머지는 최댓값으로 초기화 해주었다.

이제 모든 간선을 확인하면서 최단 거리를 업데이트 해줄 것이다.

 

A-B 간선

=> A까지의 최단 거리 + 간선 가중치는 3이다. B의 기존값과 비교하여 더 작은 최단 거리로 업데이트 해준다.

 

B까지의 최단 거리 (3) + 가중치 8 => 11로 업데이트.

 

A까지의 최단 거리 (0) + 가중치 5 => 5로 업데이트.

 

C까지의 최단 거리 (5) + 가중치 3 => 8로 업데이트.

 

D까지의 최단 거리 (8) + 가중치 -100 => -92로 업데이트.

 

C까지의 최단 거리 (5) + 가중치 12 => 기존 11 그대로 유지.

이 과정을 N-1 반복하면 E까지의 최단 거리는 -84라는 것을 알 수 있다.

 

마지막으로 음수 순환 사이클이 존재한다면 어떨까?

 

그림과 같이 음수 순환 사이클이 존재한다면 최단 거리는 계속 갱신되어야 할 것이다.

순환 사이클 존재 여부는 2번 모든 간선 탐색 과정을 한 번 더 해주면 된다.

N-1번 탐색 후, 한 번 더 탐색하여 최단 거리가 업데이트 되는 노드가 있다면 그건 음수 순환 사이클이 존재한다고 판단할 수 있다.

 

벨만 포드 알고리즘은 시간 복잡도가 O(VE)로 다익스트라 O(E logV) 보다 느리기 때문에 음수 가중치가 없다면 다익스트라, 음수 가중치가 존재한다면 벨만 포드 알고리즘으로 풀 수 있을 것이다.