116. Bellman-Ford

벨만-포드 알고리즘(Bellman-Ford Algorithm)은 한 정점에서 모든 정점까지의 최단 경로를 구하는 알고리즘이다. 이 알고리즘은 그래프의 정점의 수가 $n$, 간선의 수가 $m$일 때 시간복잡도가 $\Theta(nm)$으로 다익스트라 알고리즘에 비해 느리지만, 가중치가 음수인 간선이 존재할 경우에도 최단 경로를 찾을 수 있다. 가중치가 음수인 간선이 존재하는 그래프를 다루기 때문에, 무향 그래프는 사실상 등장하지 않으며 무향 그래프에서의 최단 경로를 다루게 된다.

 

벨만-포드 알고리즘은 다음과 같은 방식으로 작동한다.

    1. 시작 정점은 $k$, 정점 $k$로부터 정점 $i$까지의 최단 거리를 $d_i$라고 한다.

    2. 정점 $x$에서 정점 $y$로 가는 가중치 $z$인 간선이 존재할 때 $w(x, y) = z$라고 한다.

    3. $d_k$는 $0$, 나머지 $d_i$는 모두 $\infty$로 초기화한다.

    4. 각각의 간선을 확인한다. $u$에서 $v$로 가는 간선이 존재할 때, $d_u + w(u, v) < d_v$인 경우 $d_v$를 $d_u + w(u, v)$로 바꾼다.

    5. 4번 과정을 $(n-1)$번 반복한다.

    6. 4번 과정을 한 번 더 반복하는데, 이때는 $d_i$의 값이 변하는 경우가 있는지 체크한다.

 

3번 과정까지는 다익스트라 알고리즘의 작동 방식에 나온 초기화와 동일하다. 이 알고리즘은 기본적으로 5번 과정이 끝난 후 $d_i$에 정점 $k$로부터 정점 $i$까지의 최단 거리가 저장된다고 간주한다. 이때 문제가 될 수 있는 것이 음수 사이클(Negative Cycle)이다. 음수 사이클은 포함된 간선들의 가중치의 합이 음수인 사이클로, 이런 사이클은 돌 때마다 경로의 길이가 줄어들기 때문에 경로에 무한히 포함되면서 최단 경로의 길이를 $-\infty$로 만들어 버린다. 따라서 시작 정점에서 음수 사이클을 거쳐서 갈 수 있는 정점들의 $d_i$ 값은 전부 $-\infty$가 된다.

 

음수 사이클이 아닌 사이클의 경우, 이런 사이클이 경로에 포함될 때 사이클을 경로에서 제거해도 경로의 길이가 늘어나지 않으므로 이런 사이클을 경로에서 모두 제거하면 최단 경로는 사이클이 없는 형태가 된다. 경로에 사이클이 존재하지 않으므로 경로에 포함되는 간선의 수는 최대 $(n-1)$이다.

 

한편 4번 과정을 $i$번째 반복하는 것의 의미를 파악해 보면 간선을 $i$개 이상 거치는 경로의 최단 거리를 구하는 것임을 알 수 있다. 간선을 $i$개 거치는 경로의 최단 거리는 4번 과정을 $i$번 이상 반복하면 구해지므로 4번 과정을 $(n-1)$번 반복하면 각각의 정점까지의 최단 거리가 구해지며, 음수 사이클이 존재하지 않을 경우 6번 과정에서 $d_i$의 값이 하나도 변하지 않아야 한다. 만약 $d_i$의 값이 하나라도 변했을 경우 그래프에 음수 사이클이 존재하는 것으로 생각할 수 있다.

 

다음과 같은 방향 그래프에서 최단 경로를 찾는 경우를 생각해 보자. 시작 정점은 $\text{G}$이다. 간선은 $\text{C} \to \text{I}, \text{G} \to \text{B}, \text{H} \to \text{E}, \text{F} \to \text{E}, \text{A} \to \text{I}, \text{D} \to \text{B}, \text{C} \to \text{G}, \text{A} \to \text{D}, \text{G} \to \text{F}, \text{B} \to \text{H}, \text{A} \to \text{G}, \text{E} \to \text{B}, \text{F} \to \text{C}$ 순서로 확인한다고 가정한다.

이제 각각의 간선을 확인하는 과정을 시작한다. 첫 번째로 간선을 확인할 때는 $\text{G} \to \text{B}, \text{G} \to \text{F}, \text{B} \to \text{H}, \text{F} \to \text{C}$ 간선에서 $d_v$의 값이 변경된다.

주의해야 할 점이 있다면, $d_u = d_v = \infty$이고 $w(u, v) < 0$일 때 $d_v$를 갱신하지 않아야 한다는 것이다. 문제를 풀 때는 실제로 $\infty$를 $d$ 배열에 저장하지 않고 최단 거리가 될 수 없는 큰 값을 $\infty$를 나타내는 값으로 사용하는 경우가 많은데, 이런 상황에서 구현을 잘못하면 $\infty$로 초기화된 값이 갱신되는 상황이 생길 수도 있으므로 이것을 방지해 주어야 한다. 위 그래프의 경우, $\text{H} \to \text{E}$ 간선을 확인할 때 $d_\text{H} = d_\text{E} =\infty$이고 $w(\text{H}, \text{E}) = -8$이지만 $d_\text{E}$가 $(\infty - 8)$로 변경되는 일은 없어야 한다.

 

두 번째로 간선을 확인할 때는 $\text{C} \to \text{I}, \text{H} \to \text{E}, \text{E} \to \text{B}$ 간선에서 $d_v$의 값이 변경된다.

나머지 여섯 번의 확인에서는 $\text{H} \to \text{E}, \text{B} \to \text{H}, \text{E} \to \text{B}$ 세 간선들 중에서만 $d_v$의 값이 변한다.

세 번째 확인

 

네 번째 확인

 

다섯 번째 확인

 

여섯 번째 확인

 

일곱 번째 확인

 

여덟 번째 확인

 

아홉 번째로 간선들을 확인할 때 값이 변하는 $d_v$가 존재하므로 이 그래프에 음수 사이클이 있다는 것을 확인할 수 있다.

이 그래프의 경우 정점 $\text{A}$, $\text{D}$는 정점 $\text{G}$에서 갈 수 없으므로 $d_i$ 값이 $\infty$이며, 정점 $\text{B}$, $\text{E}$, $\text{H}$는 음수 사이클을 거쳐서 갈 수 있으므로 $d_i$ 값이 $-\infty$이며, 나머지 정점 $\text{C}$, $\text{F}$, $\text{G}$, $\text{I}$의 $d_i$ 값은 정수로 나타난다.

 

간선을 $n$번 확인한 상태에서는 어떤 정점들의 $d_i$ 값이 $-\infty$인지 제대로 확인할 수가 없다. 하지만 음수 사이클을 거쳐서 갈 수 있는 정점들의 $d_i$ 값은 간선을 $n$번 확인한 이후에도 계속 변하므로, 간선을 $n$번 더 확인했을 때 $d_i$ 값이 한 번 이상 변했다면 $d_i$의 실제 값은 $-\infty$라고 할 수 있다.

 

구현은 다음과 같다. 벨만-포드 알고리즘의 경우 vector 배열 대신 구조체 배열을 써서 구현해도 불편하지 않다.

#import<bits/stdc++.h>
using namespace std;
int d[1005];
vector<pair<int, int>>e[1005];
int main()
{
    int k, m, n, x, y, z;
    cin >> n >> m >> k;
    for(int i = 1; i <= m; i++)
    {
        cin >> x >> y >> z;
        e[x].push_back({y, z});
    }
    fill(d + 1, d + n + 1, 1 << 30);
    d[k] = 0;
    for(int t = 1; t < n; t++)
    {
        for(int i = 1; i <= n; i++)
        {
            for(auto &p: e[i])d[p.first] = min(d[p.first], d[i] + p.second);
        }
    }
}

음수 사이클의 존재 여부도 확인해야 하는 경우 $t$를 $n$까지 반복하면서 $t = n$일 때 $d_i$ 값이 변하는 경우가 있는지 체크하면 된다.

 

벨만-포드 알고리즘은 등장 빈도가 많지는 않으며, 다른 최단 경로 알고리즘인 SPFA로 대체되는 경우도 꽤 있다.

 

[연습문제]

 

BOJ 11657. 타임머신 (Gold IV)

음수 사이클이 있는지 확인하고, 음수 사이클이 없다면 각 정점까지의 최단 거리를 출력하면 된다.

 

BOJ 1865. 웜홀 (Gold III)

문제를 다시 해석하면, 그래프에 음수 사이클이 있는지 확인하면 된다. 주어지는 그래프가 연결 그래프가 아닐 수도 있으므로 각 컴포넌트마다 음수 사이클이 있는지를 체크해야 한다.

 

BOJ 13317. 한 번 남았다 (Gold III)

음수 사이클이 없는 그래프에서 간선들을 확인하는 과정을 $(n-1)$번째 반복했을 때 변하는 $d_i$ 값이 존재한다는 것은 간선 $(n-1)$개를 거쳐야 하는 최단 경로가 존재한다는 의미이다. 따라서 이런 최단 경로가 생기는 그래프를 찾아서 출력하면 된다.

 

→ solved.ac tag: bellman_ford