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

벨만-포드 알고리즘 (Bellman-Ford Algorithm)이란?

다익스트라 알고리즘과 같이 특정 노드 사이의 최단거리를 구하기 위한 알고리즘이다. 초기에 모든 정점의 값을 무한으로 초기화하고 길이를 최단거리로 계속 업데이트하는 방식이다. 벨만 포드 알고리즘의 가장 큰 특징은 음수 가중치가 존재한다는 점이다. 다익스트라 알고리즘의 경우 음수 가중치가 존재하지 않아 몇 번의 반복만으로 최단거리를 구할 수 있지만 벨만 포드 알고리즘은 음수 가중치 때문에 무한히 업데이트되는 경우가 생길 수 있다. 이 때에는 강제로 업데이트를 종료해야 한다. 아래 그림을 통해 확인해보자. 

일단 기본적인 그래프가 아래와 같다고 하자. 

시작점 A를 제외한 모든 정점을 무한으로 초기화해준다. 이제 A점을 시작으로 A와 연결된 모든 점을 돌면서 최단 거리를 업데이트해준다. 순서는 A->B , A->D , A->E 순서로 업데이트해주면 되겠다.
우선 A->B의 가중치가 -1이며 B 노드의 값이 무한이므로 최소가 -1이 되므로 B의 값을 -1로 업데이트 해준다. 마찬가지로 D, E에 대해서도 각각 2, 3으로 업데이트 해준다. 그렇다면 아래의 그림과 같이 나온다.

이제 A에 대한 업데이트는 끝났다. 다음은 B에서 다른 노드까지에 대한 경로 업데이트를 해준다. B와 연결된 노드는 C, D이다. 따라서 탐색 순서를 B->C, B->D 로 정하면 되겠다.
B->C에서 C의 최소값이 무한이므로 B에서 C의 가중치인 -1 + 3 = 2보다 크다. 따라서 C의 값을 3으로 업데이트해준다. D의 값은 이전에 A로부터의 경로 탐색에서 한번 업데이트가 되서 현재 2의 값을 가지고 있는데, B->D의 가중치인 -1-2 = -3 보다 크기 때문에 D의 값을 -3으로 업데이트 해주자.

이와 같은 방법으로 한 점에서부터 모든 정점에 대해서 탐색을 하면 1 사이클을 돌게 된다. 그렇다면 해당 알고리즘은 한 사이클에서 최소값을 구할 수 있을까? 어떤 수에서 음수 가중치를 더하게 되면 그 값은 기존의 값보다 작아지게 된다. 즉, 음수 가중치가 존재한다면 최단 경로가 무한히 업데이트된다. 따라서 이 경우 적당히 종료를 해야하겠다. 즉 음수 가중치가 존재할 경우 최단 경로를 구할 수는 없지만, 음수 가중치가 존재하는지에 대한 것 정도는 판단할 수 있다.
이와 관련해서 백준에 풀어볼만한 문제가 하나 있다. 

백준 1865. 웜홀

문제

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

풀이

일단 기본적인 아이디어는 위의 벨만 포드 알고리즘을 이용하면 된다. 단, 위에서 벨만 포드 알고리즘을 이용할 경우 음수 가중치가 존재할 경우 무한히 업데이트가 될 수 있다고 했는데, 이 문제의 경우 업데이트를 언제 종료해줘야 할까? 별로 상관이 없다. 문제에서 "처음으로 돌아왔을 때 시간이 줄어들었을 경우 yes를 출력"하라고 했다는 것은, 사이클을 돌 때마다, 이전 값보다 업데이트 된 값이 더 작을 때 yes를 출력해주면 될 뿐이다.

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>

using namespace std;

int N, M, W;

vector<vector<pair<int, int> > > v(510);
int res[510];


bool check(){

    for(int i = 0; i <= 500; i++){
        res[i] = 99999999;
    }
    res[1] = 0;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            for(int k = 0; k < v[j].size(); k++){
                if(res[j] + v[j][k].second < res[v[j][k].first]){
                    res[v[j][k].first] = res[j] + v[j][k].second;
                    if(i == N) return true;
                }
            }
        }
    }

    return false;
}

int main(){

    ios::sync_with_stdio(false);
	cin.tie(NULL);
    cout.tie(NULL);

    int T; cin >> T;
    for(int i = 0; i < T; i++){
        cin >> N >> M >> W;
        v.resize(510);

        for(int j = 0; j < M; j++){
            int s, e, t; cin >> s >> e >> t;
            v[s].push_back(make_pair(e, t));
            v[e].push_back(make_pair(s, t));
        }
        for(int j = 0; j < W; j++){
            int s, e, t; cin >> s >> e >> t;
            v[s].push_back(make_pair(e, -t));
        }

        if(check()) cout << "YES" << '\n';
        else if(!check()) cout << "NO" << '\n';
        v.clear();
    }
    
    return 0;
}

소스코드 : https://github.com/betterafter/BaekJoon/blob/master/1865.cpp