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

벨만 포드 알고리즘이란?

 

 

다익스트라 알고리즘처럼 최단경로를 구해주는 알고리즘이다. 시간복잡도는 다익스트라 알고리즘보다 오래 걸리는 $O(|V||E|)$이지만 간선의 가중치가 음수일 때 사용 가능하다. 다익스트라 알고리즘으로는 간선의 가중치가 음수일 때 계속해서 갱신이 일어나므로 무한 반복이 일어나 최단경로를 제대로 구하지 못할 수 있으므로 벨만 포드 알고리즘을 사용한다. 벨만 포드 알고리즘의 핵심은 음수 가중치의 판단이고, 이는 최단 경로가 갱신되는 횟수로 구한다.

 

 

다익스트라 알고리즘에서 특정 정점에 대한 최단경로 갱신은 최대 몇 번 일어날 수 있을까? 먼저 가능한 최단 경로의 길이(거치는 정점의 수)를 생각해보자. 모든 정점을 최대 1번만 지날 수 있으므로 그 길이는 |V|이다. 또한 최단 경로 갱신 횟수는 최대 |V|-1번일 것이다.

특정 정점을 추가로 반영하여 탐색을 진행하는 과정이 |V|-1번 존재하기 때문이다.

 

 

그렇기 때문에 특정 정점에 대한 최단경로 갱신이 |V|번 이상 발생한다면 이는 음수 사이클의 존재를 나타낸다. 벨만 포드 알고리즘은 이점을 이용한다.

 

 

벨만 포드 알고리즘

 

 

간선을 저장하고 있는 벡터 E = ((u1, v1), (u2, v2), ...)가 있다고 하자. 이 벡터를 한 번 탐색하며 "만약 최단 경로를 구하는 과정에서 u를 방문했었고, 간선 (u, v)에 의해 dist(v)가 갱신될 수 있다면" dist(v)를 갱신한다.

 

최단경로를 구하는 과정에서 u를 방문했다는 것은 dist(u) != inf 이고, dist(u) + c(u, v) < dist(v)이면 갱신된다.

 

이렇게 E를 탐색하는 과정을 |V|-1번 반복하면 위에서 언급한 성질에 의해 최단 경로가 모두 구해진다.(단, 모든 c(u, v)>0)

이제 E를 한 번 더 탐색하고 만약 갱신이 일어난다면 음수 사이클의 존재를 확인할 수 있게 된다.

 

 

const long long INF=999999999;
for(int i=1; i<=n; i++){ dist[i]=INF; }
dist[1]=0;
bool f=0;
for(int i=0; i<n; i++){
    for(int j=1; j<=n; j++){
        for(auto &k : adj[j]){
            int nxt=k.first;
            long long cost=k.second;
            if(dist[j]!=INF && dist[nxt]>dist[j]+cost){
                dist[nxt]=dist[j]+cost;
                if(i==n-1){ f=1; }
            }
        }
    }
}

 

 

 

다음과 같은데(전체 코드는 하단에 있다)

 

 

다익스트라 알고리즘과 같이 dist 배열을 초기화해준다. 그리고 변수 f는 음수 가중치를 가지는 간선이 있다면 1, 없다면 0을 나타내는 변수이다.

 

반복문에서 $i$는 단순히 $n$번 반복하기 위해 사용하는 것이고, $j$는 정점들을 나타낸다. 

 

$dist[u]$!=INF인 정점 $u$(이미 1번 이상 방문한 정점)에서 인접한 정점의 최단경로를 갱신해준다. ($dist[u]$!=INF라는 것은 최단경로 값이 이미 정해진 정점 $u$라는 뜻이다)

 

 

즉, $dist$ 값이 $0$인 $1$번 정점과 인접한 정점들부터 갱신된다.

 

 

if(i==n-1){ f=1; }

 

간선을 갱신해주었는데 반복횟수가 $n$번째, 즉 마지막 반복을 하고 있는데 간선이 갱신되었다면 음수 사이클이 있다는 것으로 해석이 가능하다. 만약 음수 사이클이 있다면 최단경로가 계속해서 갱신될 것이기 때문이다.

 

 

 

 

 

 

따라서 마지막 반복을 하고 있는데 최단경로가 갱신된다면 음수 사이클이 있다고 판단할 수 있다.

 

 

#include <iostream>
#include <vector>

using namespace std;

int n, m;

vector< pair<int, long long> > adj[501];
long long dist[501];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i=1; i<=m; i++){
        int s, e; long long c;
        cin >> s >> e >> c;
        adj[s].push_back({e, c});
    }
    for(int i=1; i<=n; i++){ dist[i]=999999999; }
    dist[1]=0;
    bool f=0;
    for(int i=0; i<n; i++){
        for(int j=1; j<=n; j++){
            for(pair<int, long long> k : adj[j]){
                int nxt=k.first;
                long long cost=k.second;
                if(dist[j]!=999999999 && dist[nxt]>dist[j]+cost){
                    dist[nxt]=dist[j]+cost;
                    if(i==n-1){ f=1; } //음수 사이클이 있다고 판단
                }
            }
        }
    }
    if(f){ cout << "-1\n"; } //음수 사이클이 있다면
    else{
        for(int i=2; i<=n; i++){
            cout << (dist[i]==999999999 ? -1 : dist[i]) << "\n";
        }
    }
    return 0;
}

 

 

이 알고리즘은 MCMF 알고리즘을 할 때 SPFA 알고리즘으로 응용되어 사용된다.