[Bellman-Ford's Algorithm] 벨만-포드 알고리즘

그래프에서 최단 거리를 구할 때 자주 쓰이는 알고리즘이다. 

 

 벨만-포드 알고리즘의 장점부터 먼저 알아보자.

1. 거리의 가중치가 음수여도 사용이 가능하다.

2. 음수 사이클 여부의 존재를 알 수 있다.

위의 두 가지만 봐도 벨만포드 알고리즘의 실질적 필요성을 느낄 수 있다. 왜냐면 전에 배운 다익스트라 알고리즘은 음의 가중치가 있으면 사용이 불가능했기 때문이다. 그럼 작동과정을 살펴보자.

 

작동 과정

1. 시작 노드부터 "노드와 연결된 모든 간선"을 탐방하면서 데이터를 갱신한다.

2. 그 다음 노드와 연결된 모든 간선을 탐방하면서 데이터를 갱신한다.

3. 그 다음 노드의 다음노드와 연결된 모든 간선을 탐방하면서 데이터를 갱신한다.

4. 반복한다.

되게 간단하다. 처음 노드에 연결되어있는 모든 간선을 확인하고 거리를 갱신한다. 그 다음 노드를 선택하고 모든 간선을 확인하고... 이 과정을 반복하면 된다. 조금의 이해를 더 돕기 위해서 그림과 함께 살펴보자.

 

처음의 상태는 다음과 같다. 음의 정수가 존재하고, 사이클이 없는 그래프이다. 시작점을 1로 두고, 1과 연결되어있는 간선을 모두 활성화 해보자.

 

자기 자신과의 거리는 0이다. inf보다 각각 노드로 가는 수가 작기 때문에 거리를 갱신해준다. 다음은 2를 선택해보자.

 

(1 -> 4)로가는 3의 거리보다 (1->2->4)로 가는 거리인 -5가 더 작으므로 거리를 갱신해준다. 다음으로는 3을 활성화 시킬 건데 3에게는 갈 수 있는 간선이 없으므로 4까지 활성화 해보자.

 

이때는 4->5로 가는 간선이 활성화 되어서 기존에 있던 1->5의 간선과 (1->2->4->5)의 간선을 비교해서 더 작은값인 거리로 갱신해주었다.

 

5가 활성화 됨으로써 3까지 가는 거리가 (1->3)의 거리에서 (1->2->4->5->3)의 거리로 바뀌었다. 이런식으로 전체의 노드 개수만큼 간선을 활성화 시켜주면 된다. 

 

시간 복잡도는 어떻게 될 것인가? V마다 모든 E를 탐색해주었기 때문에 O(|V||E|)임을 쉽게 파악할 수 있다.

 

 

자 여기서 하나 더 생각해보자. 저기서 실질적으로 사용하게 된 간선은 어떤것이 있을까?

바로 다음과 같이 4개의 간선을 사용했다. 이것이 의미하는 바가 무엇일까?

 

최단거리를 구한다는 것은 사이클이 생기면 안된다는 것이다. 쉽게 얘기하면 같은 점을 두 번이상 방문하면 안된다.

계속해서 사이클이 생긴다는 얘기는 -INF의 값까지 가는 경우도 생기게 된다. 이게 최단거리일까? 당연히 아니라고 생각한다. 사이클이 생기지 않고 모든 노드가 연결되어 있으려면 그래프의 성질에 의해 V - 1개의 Edge를 선택하면 된다. 이를 코드에서 판단 해보자.

 

 

const int INF = 987654321;
int cost[N+1];
vector<pair<int,int>> tree[N+1];
 
int main(){
    // 최대 거리로 갱신
    for (int i=1;i<=N;i++){
        cost[i] = INF;
    }
    
    cost[1] = 0; // 자기 자신은 0
 
    
    bool cycle = false; // 음수 사이클 존재 여부
 
      // 경로의 길이는 최대(N-1) 이고 N일 때 갱신이 된다면 음수사이클 생긴다.
    for (int i=1;i<=N;i++){
        // 모든 정점에 대해서 모든 간선을 탐색한다.
        for (int j=1;j<=N;j++){
            for (auto &n : tree[j]){
                  // 방문되지 않은 지점에서 출발은 SKIP
                if (cost[j] != INF && cost[n.first] > n.second + cost[j]){
                    cost[n.first] = n.second + cost[j];
                    
                    if (i==N){
                         cycle = true; // N인 상태에서 거리가 갱신이 된다면 사이클이 생긴 것이다.
                    }
 
                }
            }
        }
    }
    
    // 사이클이 생겼다면 -1출력    
    if (cycle){
         cout << "-1";
    }
    // 생기지 않았다면 자기 자신을 제외하고 cost출력
    else {
        for (int i=2;i<=N;i++){
            if (cost[i] == INF){
                 cout << "INF ";
            }
            else{
                 cout << cost[i] << " ";
            }
        }
    }
}