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

Bellman-Ford 알고리즘이란?

Bellman-Ford 알고리즘이란, 한 노드에서 다른 노드까지의 최단거리를 구하는 알고리즘입니다. 벨만포드 알고리즘 외에 최단거리를 구하는 알고리즘은 여럿 있지만 벨만포드는 가중치가 음수 일 때도 사용이 가능합니다. 하지만 다익스트라 알고리즘에 비해 느리므로 가중치가 모두 양수일 경우에는 굳이 벨만포드 알고리즘을 사용할 필요가 없습니다.

 

음수간선

음수간선이 있을 경우 어떠한 문제가 생길지 알아보도록 하겠습니다.

그래프 예시

 

아래 그래프에서 s 에서 출발하여 g 로 도착하는 경우를 생각해봅시다.

• s -> a -> b -> g

  이 경우도 물론 음수간선이 존재합니다. 하지만 문제가 되는 경우는 없습니다. 3+(-4)+4 로 가중치 3으로 도착할 수 있습니다.

• s -> c -> d -> g

  음수간선이 사이클로 존재합니다. 하지만 이 경우 사이클을 순환할 이유가 없습니다. c->d->c->d ... 을 반복할수록 오히려 가중치만 늘어나게 됩니다.

• s -> e -> f -> g

  이 경우 문제가 생깁니다. 음수간선이 사이클로 존재하면서 사이클을 순환할수록 가중치는 감소하게 됩니다. 따라서 이 경우에는 해당 사이클을 순환하고 g 에 도착하는 건 가중치는 낮더라고 실절적인 최단경로라고 볼 수 없습니다.

위 경우를 보고 다음과 같은 결론을 내릴 수 있습니다.

최단경로는 순환을 포함해서는 안되므로 경로의 길이는 최대 |V|-1 이다.

 

알고리즘

벨만포드에 대한 수도코드를 보면서 알고리즘을 이해해보도록 하겠습니다.

벨만포드 알고리즘 수도코드

최단경로는 순환을 포함해서는 안되므로 경로의 길이는 최대 |V|-1 개 입니다. 그리고 각 정점에 대해서 정점과 연결된 모든 간선을 확인하며 RELAX 를 해줍니다.

RELAX 는 해당 정점에 대해서 더 낮은 가중치로 도달할 수 있는 경우, 그 값을 갱신해주는 것을 말합니다.

그 후 다시 모든 간선에 대해서 RELAX 를 검사해줍니다. 만약 그렇다면 위 그래프 이미지에서 s->e->f->g 와 같이 음수간선으로 인한 사이클이 있다는 의미입니다. 따라서 false 를 반환해주고 아니라면 true 를 반환해주도록 합니다.

 

시간복잡도

위에서 봤듯이 경로의 길이는 최대 |V|-1 입니다. 즉 |V|-1 까지만 반복해주고 그 이상이 된다면 사이클이 생기므로 멈춰줘야합니다. 각 반복에 대해서는 해당 정점과 연결되어 있는 모든 간선을 탐색해주어야 합니다. 따라서 시간복잡도는 O(|V||E|)가 됩니다.

이 때 그래프의 간선이 많으면 보통 정점의 개수의 제곱 개 정도 존재하게 됩니다. 따라서 E = V^2 , O(V^3) 의 복잡도라고 볼 수 있습니다. 다익스트라가 O(V^2) 인데 비해 복잡도가 높습니다. 따라서 음수 가중치가 있어서 벨만포드를 사용해야하는 경우가 아니라면 다익스트라를 사용하는게 일반적으로 더 빠릅니다.

 

구현

https://www.acmicpc.net/problem/11657

불러오는 중입니다...

백준에 벨만포드를 사용하는 문제가 있어 해당 문제의 풀이입니다.

#include <iostream>
#include <vector>

using namespace std;

#define INF 987654321

int dist[502];
vector<pair<int,int>> v[502];

int main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // 정점,간선의 수
    int N,M;
    cin >> N >> M;
    
    bool cycle = false;
    
    for (int i=0;i<M;i++){
        int node1,node2,w;
        cin >> node1 >> node2 >> w;
        v[node1].push_back(make_pair(node2, w));
    }
    
    for (int i=1;i<=N;i++){
        dist[i] = INF;
    }
    
    dist[1] = 0;
  	// 경로의 길이는 N-1 이고 N 이 된다면 음수사이클 생긴다.
    for (int i=1;i<=N;i++){
        // 모든 정점에 대해서 모든 간선을 탐색한다.
        for (int j=1;j<=N;j++){
            for (auto &n : v[j]){
              	// 방문되지 않은 지점에서 출발은 SKIP
                if (dist[j] != INF && dist[n.first]>n.second + dist[j]){
                    dist[n.first] = n.second + dist[j];
                    if (i==N) cycle = true;
                }
            }
        }
    }
    
    if (cycle) cout << "-1\n";
    else {
        for (int i=2;i<=N;i++){
            if (dist[i] == INF) cout << "-1\n";
            else cout << dist[i] << "\n";
        }
    }
}