[ 개념 ] 38. 벨만포드(Bellman-Ford) 알고리즘

> 벨만포드 알고리즘

---

이어서 소개해드릴 것은 또다른 최단경로 알고리즘입니다.

벨만 포드 알고리즘(Bellman-Ford algorithm)인데요, 알고리즘을 개발한 두 학자의 성을 따서 붙인 이름이라고 합니다.

동시에 독자적으로 알고리즘을 개발했던 또다른 학자의 이름까지 붙여서 벨만 포드 무어 알고리즘이라 명명할 때도 있다는군요.

다익스트라 알고리즘과 마찬가지로 시작점을 정해 주면 다른 모든 정점으로의 최단 경로를 구하는데,

다익스트라 알고리즘보다는 시간이 오래 걸려서 O(VE)의 시간이 걸리지만

이 알고리즘은 간선 cost가 음수일 때도 사용할 수가 있습니다!!

아니 도대체 거리가 음수라니 무슨 소리냐, 뭐 그런 거 다 떼어놓고 그냥 최단거리가 정말 작으면 작을수록 좋다고 친다면, 설령 그게 음수가 되더라도 정확히 구해버린다는 거죠.

그나마 말이 되는 예시를 들자면 거리 대신 이동시간이라 생각하고, 타임머신을 타서 과거로 간다고 생각하는 겁니다. 이때는 시간을 역행했으므로 소요시간이 음수가 될 겁니다.

예를 들어 이런 그래프가 있다고 합시다. 시작점이 0번 정점인데, 2번 정점까지의 최단거리를 구하려고 합니다.

이제부터는 간선 비용 자체가 음수일 수도 있어서, 그냥 최단거리 자체의 정의를 최소의 cost(음수가 되어도 상관없음)를 들여서 오는 경로의 cost 합이라 보는 게 좋겠죠.

여튼 2번 정점까지 가는 최단거리는 0->1->2를 거쳐서 12+(-7)=5여야 합니다.

그러나 다익스트라 알고리즘은 1, 2번 정점 중에서 dist[1]=12 > dist[2]=8이라 해서 2번 정점을 방문해버리게 되고, 실제 2번 정점까지의 최단 경로는 8보다 작기 때문에 이는 잘못되었으며

결국 다익스트라 알고리즘으로는 음의 간선이 존재하는 그래프에서 최단경로를 제대로 못 구할 수 있다는 사실을 보여줍니다.

따라서 벨만 포드 알고리즘은 2중 for문을 통해 철저하게 가능한 모든 경우를 다 체크하기로 합니다.

일단, 최단 경로라는 말은 같은 정점을 두 번 지날 일이 없기 때문에 가능한 최단 경로의 간선 개수는 많아봐야 V-1개입니다.

(뭔가 이상한 점을 느끼셨을지도 모릅니다. 그건 있다가 설명하겠습니다.)

따라서 루프를 V-1번 돌리는데, k번째 루프에서는 시작점으로부터 각 정점으로 k개의 간선을 거쳐서 도달할 수 있는 최단경로를 다 갱신해주자는 게 기본 아이디어입니다.

k-1번째 루프까지는 최대 k-1개 간선을 거치는 최단경로를 다 구해놓았다고 믿고(???) k번째 루프에서 그 정보들을 사용해 또다른 최단경로를 구해보는 것이죠.

- BOJ[11657]:타임머신

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

이 문제를 벨만 포드 알고리즘으로 풀어버리려고 하는데요.

#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
typedef pair<int, int> P;
const long long INF = 1e18; // 절대 나올 수 없는 경로값

int main(){
    int N, M;
    long long dist[500];
    scanf("%d %d", &N, &M);
    vector<P> adj[500];
    for(int i=0; i<M; i++){
        int A, B, C;
        scanf("%d %d %d", &A, &B, &C);
        adj[A-1].push_back(P(B-1, C));
    }
    fill(dist, dist+N, INF);
    dist[0] = 0;
    for(int i=0; i<N-1; i++){ // (N-1)번의 루프
        for(int j=0; j<N; j++){
            // N-1번의 루프에 걸쳐 각 정점이 i+1개 정점을 거쳐오는 최단경로 갱신
            for(auto &p: adj[j]){
                int next = p.first, d = p.second;
                if(dist[j] != INF && dist[next] > dist[j] + d){
                    dist[next] = dist[j] + d;
                }
            }
        }
    }
    for(int i=1; i<N; i++)
        printf("%lld\n", dist[i]!=INF ? dist[i] : -1);
}

일단 코드는 이렇습니다. 다익스트라 알고리즘과 큰 구조가 다른데요.

일단 말씀드린 대로 V-1번의 루프를 돕니다. 이 문제에서는 V = N이죠.

그리고 안쪽의 구조는 사람마다 판이하게 다를 수 있는데, 다 하는 건 똑같습니다.

존재하는 모든 간선을 돌아보면서 이 간선을 통할 수도 있는 최단경로들의 거리를 갱신하는 것.

이때, 음의 간선이 존재하기 때문에 간선 (u, v)를 볼 때 먼저 dist[u]가 아직 INF인지 확인을 해야 합니다.

구현에 따라서 둘 다 시작점에서 도달 불가능한 정점 u, v가 존재하고 (u, v) 가중치가 음수일 때

dist[u] = INF, dist[v] = INF-cost 꼴이 나올 수도 있고, 이러면 골치 아파집니다.

가장 간단한 그래프를 하나 예로 들어봅시다. u가 시작점이고 처음엔 이 상태로 시작하죠.

첫 번째 루프가 돌기 전에는 dist[v] = INF이기 때문에 간선 (v, w)는 의미가 없습니다.

의미가 있는 것은 dist[u] ≠ INF인 u이고, u에서 시작한 간선들이 인접한 정점의 dist를 갱신해주죠.

사실, 방문 순서에 따라 우연히도 (u, v)를 먼저 방문하고 dist[v]를 갱신하고 나서 (v, w)를 방문하면 한 번에 dist[w]까지 구해질 것이지만,

그 적절한 방문 순서를 알 방도가 없죠. 모르니까 우린 무식하게 가능한 경우를 다 따져보고 있는 것이구요.

따라서 최악의 사태를 대비하여 루프를 V-1번 돌리는 것이고, V-1번의 루프를 돌리면 아무리 운 나쁘게 갱신이 지연되어도 반드시 dist 값들이 모두 최단 거리를 담고 있게 됩니다.

그 다음 루프에 제일 먼 정점인 w의 거리도 비로소 구해지게 됩니다.

이때, 정점이 3개고 루프 2개로 모든 게 끝났죠.

이번엔 다른 경우를 살펴볼 겁니다.

전체 그래프의 일부만 살펴볼 건데, 이런 경우도 존재할 수 있습니다.

v, w가 어쩌다 보니 시작점과 좀 가까워서 미리 저런 dist 값을 갖고 있고,

뒤늦게 정점 u의 dist 값이 갱신되어서 이런 형태를 마주할 수 있는데요.

지금 보면 dist[u] = 2기 때문에 정점 u를 거쳐가면 dist[v]가 갱신됩니다.

dist[v]가 갱신된다면, 그 뒤에 계단식으로 dist[w]까지 갱신되어야 할 겁니다.

그래서 이번 루프에서 먼저 dist[v]가 갱신됩니다.

아직 dist[w]는 갱신되지 않을 수도 있습니다.

그러나 다음 번 루프에서는 dist[w] 역시 반드시 갱신될 수밖에 없습니다.

이때, 아직 루프가 많이 남았다면 동시에 dist[u]가 더 줄어들 수도 있습니다.

그럼 뭐, 똑같이 연쇄적으로 계속 dist[v], dist[w]도 줄어들고... 그런 겁니다.

그런데, 음의 가중치가 있는 그래프에서 최단경로를 구할 때 항상 염두에 두어야 하는 것이 있습니다.

이 그래프에서, 0번 정점에서 4번 정점으로 가는 최단거리가 얼마라고 생각하시나요?

저 빨간색 정점들을 잘 보세요. 일단 싸이클이긴 한데,

평소엔, 아니 지금까지는 최단거리는 같은 정점을 두 번 이상 지나지 않는다고 철석같이 믿고 살아왔건만,

저 싸이클을 보세요. 1->2->3->1을 순회하면 오히려 처음 1번 정점을 방문했을 때보다 시간이 줄어듭니다!!!!

3+(-4)+(-1)=(-2)만큼 시간이 역행해버리는 거죠.

문제는 이게 싸이클이라, 이 싸이클을 계속해서 돌면 시간이 언제까지고 줄어들 수가 있습니다.

게다가 이러한 싸이클에서 지금 4번 정점으로 갈 수가 있기 때문에, dist[4]는... 그렇습니다. -∞가 됩니다...

빨간색 싸이클 안에 속해있는 놈들도 말할 것이 없이 다 -∞입니다.

시작점인 0번 정점만이... 싸이클에서 도달할 수 없으므로 최단거리가 실수 범위에서 정해지게 됩니다.

이렇게 가중치 합이 0보다 작은 싸이클을 음수 싸이클 혹은 음의 싸이클(negative cycle)이라고 하며, 벨만 포드 관련 문제에서 반드시 등장하는 요소입니다.

다행히도 이 문제에서는 음의 싸이클이 하나라도 존재하면 그냥 다 필요없고 "-1" 하나만 출력하라고 명시해 주었으므로, 그냥 그걸 찾기만 하면 되는데요.

그럼 어떻게 찾을까요? 우리가 V-1번만 루프를 돌았고 이 이상 루프를 돌아봐야 최단거리들이 갱신되지 않으리라고 했죠.

그러나 만약 음의 싸이클이 존재한다면, 그 이후에 루프를 돌면 최단거리가 갱신되는 일이 발생합니다.

싸이클에 속하는 정점들부터, 그 싸이클의 인접한 정점들로까지.

따라서 음의 싸이클의 존재여부만 판단한다면 맨 마지막에 확인차 루프를 한 번 더 돌아서 최단거리가 갱신되는 일이 있는지 보면 됩니다.

#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
typedef pair<int, int> P;
const long long INF = 1e18; // 절대 나올 수 없는 경로값

int main(){
    int N, M;
    long long dist[500];
    scanf("%d %d", &N, &M);
    vector<P> adj[500];
    for(int i=0; i<M; i++){
        int A, B, C;
        scanf("%d %d %d", &A, &B, &C);
        adj[A-1].push_back(P(B-1, C));
    }
    bool minusCycle = false;
    fill(dist, dist+N, INF);
    dist[0] = 0;
    for(int i=0; i<N; i++){ // (N-1) + 1번의 루프. 마지막은 음의 싸이클 존재 여부 확인용
        for(int j=0; j<N; j++){
            // N-1번의 루프에 걸쳐 각 정점이 i+1개 정점을 거쳐오는 최단경로 갱신
            for(auto &p: adj[j]){
                int next = p.first, d = p.second;
                if(dist[j] != INF && dist[next] > dist[j] + d){
                    dist[next] = dist[j] + d;
                    // N번째 루프에 값이 갱신되면 음의 싸이클이 존재한다.
                    if(i == N-1) minusCycle = true;
                }
            }
        }
    }
    if(minusCycle) puts("-1");
    else{
        for(int i=1; i<N; i++)
            printf("%lld\n", dist[i]!=INF ? dist[i] : -1);
    }
}

아아아아주 조금 달라졌습니다. 일단 루프 도는 횟수가 한 번 늘었고,

마지막 루프에 뭔가 갱신되면 minusCycle이란 flag 변수를 set하여 음의 싸이클이 존재함을 판정합니다.

여튼, 이렇게 큰 루프가 V번이고 안쪽에서 하는 일은 형태는 다양할지언정 동일하게 모든 간선을 순회하는 것이므로 총 시간복잡도는 O(VE)가 됩니다.

여기서 상당한 맹점이 있는데, 무한 루프가 없을 때 가능한 "최단 경로"의 최댓값은 (정점 수 - 1) * (최대 거리값)이라 4byte 정수형 값의 범위 안에 들어오지만, 이 문제에서는 안전하게 8byte 정수형 값을 사용해야 합니다.

왜냐면 모든 간선이 절댓값 최대인 음의 가중치(이 문제에서는 -10000)를 가지고 있다면, N번의 루프 안에 계산 중간값의 절댓값이 4byte 정수형 값을 넘어가버릴 수 있게 됩니다.

다음과 같은 그래프를 생각해 봅시다. 정점이 1부터 N까지 있고, 간선도 N개 존재하는데 1->2, 2->3, ... -> (N-1)->N, N->1 을 이어주며, 각각의 비용이 -C(C > 0)라고 하겠습니다.

그렇다면 위 코드의 경우 첫 번째 루프에서 쭉쭉쭉 따라와서 dist[N-1] = -C(N-1)이 계산되고, 이어서 dist[0] = -CN 이 됩니다.

다음 루프에서는 최종적으로 dist[0] = -2CN이 됩니다.

그 다음 루프에서는 최종적으로 dist[0] = -3CN이 됩니다.

이 과정을 쭉 따라오면 마지막 루프에서 dist[0] = -C*N^2가 되는데요, 이 값에 문제의 최대 범위 값을 모두 투입해 보면 절댓값이 21억을 넘어가버리고 맙니다.

즉 양의 값들이 아니라 반대쪽에서 오버플로우가 일어날 가능성이 존재한다는 것입니다. 음의 비용이 있는 그래프 최단 경로 문제에서 항상 신경써야 할 어려운 점 같네요...

벨만 포드 알고리즘은 나머지 2개, 다익스트라와 플로이드에 비해 실제로 보기가 조금 어려운 유형에 속합니다.

그러나 나왔다 하면 항상 타임머신이나 블랙홀 등 과거로 가는 행동과 연관이 많습니다.

사실 그게 아니고서야 우리에게 뜬금없이 "봐봐 이 경로를 거치면 음수의 거리다."라고 하는것도 무리지만요...

또한 벨만 포드 알고리즘의 변형으로 시간복잡도는 그대로지만 실전에서 더 빠르게 돌아간다고 하는 SPFA(shortest path faster algorithm)이라는 게 있고, 다익스트라와 비슷한 코드인데 우선순위 큐가 아닌 큐를 사용한다는 점이 다릅니다.

물론 음의 가중치가 있는 그래프에 사용 가능하며, 훗날 MCMF 문제를 풀 때 애용되는 알고리즘입니다.

우선순위 큐(->다익스트라)나 유니온 파인드(->크루스칼)가 그러했듯이, 벨만 포드만 쓰는 문제보다도 MCMF 때문에 필요한 문제가 압도적으로 많습니다.

벨만포드 관련 문제

11657번: 타임머신

위에서 설명한 문제입니다.

1738번: 골목길

이 문제는 한때 도대체 출처와 정체와 지문의 뜻과 데이터의 상태 중 알 수 있는 게 한 개도 없는 정체불명의 정답률 0% 저주받은 문제였으나, 언젠가 정상적인 문제로 리메이크되었습니다.

타임머신 문제와는 좀 다르게, 음의 싸이클이 있기만 하면 끝이 아니라, 그 음의 싸이클에서 도착점으로 도달 가능해야 답이 -1입니다. 역방향 간선 리스트를 만들고 도착점으로부터 BFS를 해서 각 정점이 도착점으로 도달 가능한가 파악해 놓는 전처리가 가능합니다. 물론, 그냥 시작점에서 도착점에 도달 불가능해도 답이 -1입니다.

1865번: 웜홀 (★)

문제 자체는 상당히 간단합니다. 시작점조차 주어지지 않고, 그냥 N개 정점이 있는데 이 중 아무거나 시작점을 자신으로 했을때 자신으로 돌아오는 최단거리가 0보다 작은 경우가 하나라도 있냐고 물어보는데, 이 말을 잘 풀이해 보면 음의 싸이클이 존재하냐는 겁니다.

음의 싸이클이 시작점과 다른 먼 곳에 존재하고 음의 싸이클에서 시작점으로 못 돌아올 수도 있겠으나, 그때는 그냥 음의 싸이클 안의 정점들이 이미 문제에서 찾는 정점이기 때문에 이미 YES.

다만 이번에는 그래프를 이루는 컴포넌트가 여러 개일 수도 있다는 점을 조심하셔야 하고, 각 컴포넌트를 각 그래프로 취급하여 일일이 벨만 포드를 돌려보는 수밖에 없습니다.

물론 시간 초과의 위험이 있으니 너무 무식하게 짜지는 마시고,

상위의 visited 배열을 준비해서 방문 안 한 정점이 나타나면 그 정점을 시작점으로 하여 벨만 포드를 한 번씩 돌려주면 그 컴포넌트 안에 존재하는 음의 싸이클은 찾을 수 있을 겁니다.

이렇게 모든 정점을 순회하시면 됩니다.

10360번: The Mountain of Gold?

시작점의 과거로 돌아갈 수 있는지를 묻는 문제입니다.

N번째 루프에서 시작점으로부터의 거리가 확실히 작아지는 정점들 중 시작점으로 가는 길이 있는 정점이 있다면 가능합니다. 시작점이 그 음의 싸이클에 포함되더라도 이 성질은 성립합니다.

1219번: 오민식의 고민 (★)

정점을 지날 때마다 돈을 벌어들이는데, 돈을 벌어들이는 것은 소비하는 것과 반대되므로 음의 가중치로 부여합니다. 마침 문제에서 구하라는 것도 돈의 최댓값인데, 소지금 자체를 음수로 본다면 최소의 음수가 되겠죠.

저번에 정점에 가중치가 있는 문제를 풀었을 때처럼, 그냥 정점을 방문할 때마다 그 정점의 가중치까지 cost에 넣어주면 됩니다. 맨 처음엔 dist[S]는 -(S에서 벌 수 있는 돈)으로 시작합니다.

단, 음의 싸이클이 존재는 하더라도 도착 도시로 못 가는 경우도 존재할 수 있습니다. 따라서 음의 싸이클 안에 속해있다고 판정되는 정점이 나타날 경우, 꼭 거기서 도착점으로 도달 가능한지도 체크해 주어야 Gee 여부를 정확히 판정할 수 있습니다.

또한 결과인 최단거리는 int 범위 안이지만 도중의 연산 과정에서 이 한도를 벗어날 수 있기에 long long형 배열을 사용하셔야 합니다.

 

출처 : blog.naver.com/kks227/220796963742