Bellman-Ford

벨만-포드 알고리즘은 다익스트라와 비슷하게 한 지점에서 다른 지점으로 가는 최단 경로를 찾는 알고리즘입니다. 대신 다익스트라와 달리 음수 가중치를 가지는 간선이 있는 그래프에서도 사용할 수 있습니다.

음수 가중치

그렇게 자주 나오는 경우는 아니지만, 종종 음수 가중치를 가지는 간선이 있는 그래프가 있습니다. 음수 가중치가 있는 그래프는 다익스트라 알고리즘을 사용할 수 없기 때문에 벨만-포드 알고리즘을 고려해야 합니다. 음수 가중치가 있는 그래프에는 음수 사이클이 존재할 수 있습니다. 음수 사이클이란 음수 가중치를 가지는 간선이 순환 구조를 이루는 경우를 말합니다. 예를 들어, 아래의 그래프를 보면

1번 노드에서 5번 노드로 가는 최단 경로가 얼마일까요? 음수 가중치를 가지는 간선이 2, 3, 4번 노드 사이에 사이클을 이루고 있습니다. 이 사이클을 계속해서 돌면 거리가 무한히 작아져 정확한 최단 경로를 구할 수 없습니다. 따라서 음수 간선이 있는 그래프에서 최단 경로를 구할 때는 음수 사이클이 존재하는지 확인해야 합니다. 벨만-포드 알고리즘을 사용하면 음수 사이클이 존재하는지까지 확인할 수 있습니다.

구현

다익스트라 알고리즘은 매번 방문하지 않은 노드 중에서 가장 최단 거리가 짧은 노드를 선택하여 탐색을 진행했습니다. 벨만-포드에서는 가장 거리가 짧은 노드가 아니라 모든 노드를 탐색합니다. 그래서 다익스트라보다는 느리지만, 음수 가중치를 가지는 간선이 있는 그래프에서도 사용할 수 있습니다. 다익스트라의 시간복잡도는 \( O(E \log V) \)인 반면, 벨만-포드의 시간복잡도는 \( O(VE) \)입니다. 참고로 \( V \)는 노드의 개수, \( E \)는 간선의 개수입니다.

벨만-포드 알고리즘은 다음과 같이 동작합니다.

시작 노드를 제외한 모든 노드의 거리를 무한대로 초기화합니다.
모든 간선에 대해 최대 V-1번 반복하여 다음을 수행합니다.
1. 각 간선을 하나씩 확인해 간선을 거쳐서 다른 노드로 가는 거리가 더 짧은 경우 거리를 갱신합니다.
모든 간선을 한 번 더 확인하여 거리를 갱신할 수 있는 간선이 있다면 음수 사이클이 존재하는 것으로 간주합니다.

BOJ 11657번: 타임머신 문제는 벨만-포드 알고리즘을 적용할 수 있는 대표적인 문제입니다. 단순히 1번 노드에서 다른 노드로 가는 최단 경로를 구하면 되는 문제이지만, 음수 가중치를 가지는 간선이 존재하기 때문에 벨만-포드 알고리즘을 사용해야 합니다.

우선 인접 리스트 형태로 입력을 받고 dist 배열을 무한대로 초기화합니다. 참고로 C++에서 dist를 int로 선언하면 음수 사이클이 존재할 때 음수 오버플로우가 생길 수 있습니다. 예를 들어, 노선의 가중치가 -10,000일 때, 최대 \( 500 \times 6,000 = 3,000,000 \)번 갱신이 일어날 수 있어 int 범위를 벗어날 수 있습니다.

int n, m;
cin >> n >> m;
vector<pair<int, int>> graph[n + 1]; // {vertex, weight}

for (int i = 0; i < m; i++) {
    int a, b, w;
    cin >> a >> b >> w;
    graph[a].push_back({b, w});
}

이제 노드의 개수 - 1번만큼 모든 간선을 확인하여 거리를 계산해야 합니다. 그리고 한번 더 반복해서 음수 사이클이 존재하는지 확인해야 합니다. 그래서 이 과정을 합쳐 노드의 개수 \( n \)번 만큼 반복하는 반복문을 작성합니다. 그리고 \( n \)번째 반복에서 거리가 갱신되는 경우 음수 사이클이 존재하는 것을 알 수 있습니다. 코드를 먼저 보고 설명하겠습니다.

for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
        for (auto &[next, cost] : graph[i]) {
            if (dist[i] != 1e9 && dist[next] > dist[i] + cost) {
                dist[next] = dist[i] + cost;

                if (k == n) {
                    cout << -1;
                    return 0;
                }
            }
        }
    }
}

\( k \)는 반복 횟수를 나타냅니다. 각 반복마다 모든 노드 \( i \)에서 출발하는 간선을 확인합니다. 먼저 dist[i]가 무한이 아닌지 확인해 출발 노드에서 \( i \)번째 노드로 도달할 수 있는지 확인합니다. 그 다음 next노드로 가는 거리가 \( i \)노드를 거쳐서 가면 더 짧아지는지 확인합니다. 만약 그렇다면 dist를 갱신합니다. 마지막으로 \( n \)번째 반복이 되고, 추가적으로 거리가 갱신되는 경우 음수 사이클이 존재하는 것이므로 -1을 출력하고 종료합니다. 마지막으로 거리를 출력하면 됩니다.

최종 코드는 다음과 같습니다.

#include <bits/stdc++.h>

using namespace std;
void fio() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); }

int main() {
    fio();

    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> graph[n + 1]; // {vertex, weight}
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        graph[a].push_back({b, w});
    }

    long long dist[n + 1];
    fill(dist, dist + n + 1, 1e9);
    dist[1] = 0;

    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (auto &p : graph[i]) {
                int next = p.first;
                int cost = p.second;

                if (dist[i] != 1e9 && dist[next] > dist[i] + cost) {
                    dist[next] = dist[i] + cost;
                    if (k == n) {
                        cout << -1;
                        return 0;
                    }
                }
            }
        }
    }

    for (int i = 2; i <= n; i++) {
        if (dist[i] == 1e9) cout << -1 << '\n';
        else cout << dist[i] << '\n';
    }
}