[알고리즘] 벨만 포드 알고리즘 (Bellman-Ford)

Bellman-Ford Algorithm

이 알고리즘은  모든 간선을 전부 확인하여, 음수 가중치도 문제도 해결할 수 있습니다.

 

1. 엣지 리스트를 활용한다.

위에 언급한 것처럼, '모든 간선(엣지)'를 전부 확인함으로 엣지 리스트를 사용하는 편이 직관적이고 효율적입니다.

엣지 리스트란, 단순하게 모든 엣지 정보(시작 노드, 도착 노드, 비용)을 담은 리스트입니다.

 

2. 'update'를 노드의 개수 - 1번 만큼 반복한다.

우선, 다익스트라에서 사용한 것과 유사하게, 최소 비용 배열을 선언한 후, 모두 무한의 값으로 초기화합니다.

(최소비용배열[N] = 시작 노드에서 출발하여 N번 노드로 가는 최소비용)

이 배열의 시작 노드 값을 0으로 설정합니다.

 

이제 Update는 아래와 같습니다.

엣지 리스트를 순회하며,

최소비용배열[시작노드] != 무한 and ( 최소비용배열[도착노드] > 최소비용배열[시작노드] + 비용) 인 경우

최소비용을 갱신합니다. 

 

여기서 이해하야할 것은 Update를 1번 수행한다는 것은(즉, 모든 간선 정보에 대해하여 위의 로직을 한번씩 수행) 1개의 엣지를 거쳐서 어떤 노드로 가는 최소비용을 구했다는 뜻입니다.

 

예시를 들어보겠습니다. 

 

(A) ⟶  3 ⟶ (B) ⟶ 5 ⟶ (C) ⟶ 1 ⟶ (D) 

   ↳⟶⟶⟶⟶10 ⟶⟶⟶⤴︎ 

 

위와 같은 그래프가 있을 때 update를 한 번 수행하면 최소비용배열은[0, 3, 10, ∞] 입니다. 

두 번 수행하면, [0, 3, 8, 11]

세 번 수행하면, [0, 3, 8, 9]

 

때문에, 위의 update를 총 노드의 개수 - 1 만큼 수행하면, 최적의 해를 구할 수 있습니다. 왜냐하면, 사이클이 최악의 경우 노드의 개수 - 1개의 간선을 사용하기 때문입니다.

 

3. 'update'를 한 번 더 수행하여, 음의 순환이 있는지 확인할 수 있다.

이미 노드의 개수 - 1번을 수행하여, 노드의 개수 - 1개의 간선을 통한 최소 비용을 구했는데,

한번 더 수행했을 때 최소 비용이 갱신이 된다면, 음의 순환이 존재한다는 뜻입니다. 

 

예시를 들어보겠습니다.

 

(A) ⟶  3 ⟶ (B) ⟵ 5 ⟵ (C)

                       ↳   -10  ⟶⤴︎ 

위의 그래프에서 update를 2번 수행하면, 최소 비용 배열은 [0, 3, -7]이 되고,

한 번 더 수행하면 [0, -2, -12]가 됩니다.

 

수도코드

위의 로직을 수도 코드로 표현하면 다음과 같습니다.

 

for ( i = 1  to i = 전체 노드 개수 - 1)

        update()

 

if ( update() 후 최소 비용 배열이 갱신되면)

    return 음수 사이클 발생

 

return 최소비용배열