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

 

 벨만 포드 알고리즘은 다익스트라 알고리즘과 다르게 음수 가중치가 있는 그래프에서도 모든 정점으로 가는 최단 거리를 찾을 수 있게 해줍니다.

 

하나의 출발점에서 출발하여 모든 지점으로 가는 최단 거리를 알 수 있습니다.

 

 

1. 벨만 포드 알고리즘

 

 

 기본 아이디어는 그래프를 연결하고 있는 Edge를 기준으로 모든 정점으로 가는 최단 거리를 찾는 것입니다. 다익스트라가 정점 중심으로 최단 경로를 찾았다면 벨만 포드 알고리즘에서는 Edge들을 중심으로 찾습니다. 

 

 정점의 갯수를 V라 할 때, 한 정점에서 모든 정점을 방문할 수 있으려면 적어도 V-1번 방문해야 모든 정점을 방문할 수 있습니다. 따라서 모든 Edge들을 V-1번 보면서 각 정점의 최단 거리를 찾습니다.

 

 다만 주의할 점은 만약 처음 D->C로가는 가중치 7인 에지를 먼저 보게된다면, D 정점과 C번 정점 모두 한 번도 방문하지 않은 지점이기 때문에(값 이 무한대) 해당 Edge는 스킵해야합니다. 즉, 방문 되지 않은 정점(값이 무한대)에서 출발하는 edge는 고려하지 않습니다.

 

 

 

 

예시를 보면서 설명드리겠습니다. 출발점은 A 정점입니다.

 

정점들의 갯수가 4개이므로 총 3번 모든 Edge를 방문해야합니다.

 

 

 

 

 

 일단 무한대가 아닌 값이 A 정점밖에 없기 때문에 A 정점에서 나가는 모든 것들을 방문합니다.

 

 

 

 

 

2번째 방문입니다. A->D->B로 가는 경로와 A->D->C로 가는 경로가 추가적으로 발견되어 B, C 정점의 값이 바뀌었습니다.

 

새로운 경로가 발견되었을 때 정점이 가지고 있는 값보다 작다면 작은 값으로 갱신시켜줍니다.

 

 

 

 

 

 3번째 방문때는 어떠한 갱신도 이루어지지 않습니다.

 

 

 

 

2. 음의 사이클 검증하기

 

벨만 포드 알고리즘에서는 V-1 번 Edge들을 거치고 나면 최단 거리가 완성되는데, 한 번 더 돌리게 되면 음의 사이클이 있는 지 없는지 검증 가능합니다. 음의 사이클이란 한 노드에서 시작해 한 노드로 끝나는 경로중에 경로의 가중치를 모두 합한 값이 음수가 되는 경로를 말합니다. 따라서 V-1번째 갱신 거리와 V번째 갱신 거리를 비교했을 때 값이 달라진다면 음의 사이클이 있다고 판단할 수 있습니다.

 

위의 예시는 음의 사이클이 없는 경우 입니다.

 

 

 

 

https://www.acmicpc.net/problem/11657 (타임머신) - 벨만포드 알고리즘 기본 문제

 

#include <iostream>
#include <vector>
#include <tuple>
using namespace std;
 
vector <int> bellman(501);
vector <int> check(501);
vector <tuple<int, int, int> > edge;
int N, M;
 
int main() {
    
    cin >> N >> M;
 
    for (int i = 0; i < M; i++) {
        int A, B, C; cin >> A >> B >> C;
 
        edge.push_back(make_tuple(A, B, C));
    }
 
    bellman[1] = 0;
 
    for (int i = 2; i <= N; i++) {
        bellman[i] = 987654321;
    }
    
    // 구하기
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j < edge.size(); j++) {
            int here = get<0>(edge[j]);
            int there = get<1>(edge[j]);
            int w = get<2>(edge[j]);
 
            if (bellman[here] == 987654321) continue;
 
            if (bellman[there] > bellman[here] + w) {
                bellman[there] = bellman[here] + w;
            }
        }
    }
 
    
    // 검증
    check = bellman;
 
    for (int j = 0; j < edge.size(); j++) {
        int here = get<0>(edge[j]);
        int there = get<1>(edge[j]);
        int w = get<2>(edge[j]);
 
        if (check[here] == 987654321) continue;
 
        if (check[there] > check[here] + w) {
            check[there] = check[here] + w;
        }
    }
 
    
    bool flag = true;
 
    for (int i = 2; i <= N; i++) {
        if (check[i] != bellman[i]) {
            flag = false; break;
        }
    }
 
    if (flag) {
        for (int i = 2; i <= N; i++) {
            if (bellman[i] == 987654321) {
                cout << -1 << '\n';
            }
            else {
                cout << bellman[i] << '\n';
            }
        }
    }
    else {
        cout << -1 << '\n';
    }
 
    return 0;
    
 
}