[ 백준 11657 ] 타임머신 (벨만-포드 알고리즘)

알고리즘을 보면서도... 문제를 풀면서도 이해가 잘 가지 않아 여러 블로그의 글들을 읽어보았다. 벨만-포드 알고리즘을 공부하면서 들었던 의문점을 정리해보았다.
벨만-포드 알고리즘은 다익스트라 알고리즘과 달리 간선의 가중치가 음수일때도 동작하는 SSP 알고리즘이다.

1. 왜 간선의 가중치가 음수일때도 잘 동작할까?

A에서 B로 반경을 넓히면서 D로 가는 최단 경로가 (A->B->D)로 설정이 될 것입니다. 왜냐하면 A->B->D 경로의 비용은 100인 반면, A->B->C로 갔을 때 비용은 벌써 250으로 A->B->D의 경로를 훨씬 초과하기 때문입니다.

다익스트라 알고리즘은 그때그때의 상황에 최선의 선택을 하려는 그리디 알고리즘 기반이기 때문에 다음과 같은 상황에서는 통하지 않는다. 벨만-포드는 가능하다. 모든 경우의 수를 다 보기 때문.

2. 모든 경우의 수를 보려면 왜 V-1번 반복해야 할까

첫 번째 루프가 돌기 전에는 dist[v] = INF이기 때문에 간선 (v, w)는 의미가 없습니다. 의미가 있는 것은 dist[u] ≠ INF인 u이고, u에서 시작한 간선들이 인접한 정점의 dist를 갱신해주죠.
사실, 방문 순서에 따라 우연히도(u, v)를 먼저 방문하고 dist[v]를 갱신하고 나서 (v, w)를 방문하면 한 번에 dist[w]까지 구해질 것이지만, 그 적절한 방문 순서를 알 방도가 없죠. 모르니까 우린 무식하게 가능한 경우를 다 따져보고 있는 것이구요.
따라서 최악의 사태를 대비하여 루프를 V-1번 돌리는 것이고, V-1번의 루프를 돌리면 아무리 운 나쁘게 갱신이 지연되어도 반드시 dist 값들이 모두 최단 거리를 담고 있게 됩니다.
Ries 마법의 슈퍼마리오님 블로그에서

3. V번째 반복에서도 값이 갱신되면 음수 사이클이 존재한다는 것을 알 수 있다. 왜 그럴까?

앞서 말했듯 V-1번의 루프를 돌면 노드의 방문순서에 상관없이 모든 경우의 수를 따져볼 수 있으므로 최단 경로를 구할 수 있다. 하지만 음수 사이클이 존재하면 이 사이클을 돌기만 하면 시간이 계속 줄어들 수 있다. V-1번의 루프 이후에도 값은 계속 줄어들 것이다.

참고) 모든 사이클이 문제가 되는 것은 아니다. 시작점부터 도착점까지의 경로에 포함되는 음수 사이클만 문제가 되는 것이다.

4. res[j] != INF 왜 INF가 아닌 부분만 업데이트 해야하는 걸까? 다익스트라에선 이런 부분이 없었는데.

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

dist[u] = INF, dist[v] = INF-cost 꼴이 나올 수 있기 때문이다.

문제

타임머신 11657번

백준 타임머신 문제. 벨만-포드 알고리즘을 제대로 이해를 못한 채로 접했었기 때문에 "만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다" 이 말도 제대로 이해를 못 했었다. 대강 음수 사이클을 의미하겠거니 했지만 정확히 이해는 못 했었는데, 음수 사이클을 돌기만 하면 최단 경로가 갱신되므로 '무한히 오래 전으로 되돌릴 수 있다' 라고 표현한 것이다.

보통 경로를 지났는데 시간은 덜 걸린다는게 이상해서 실제로 접하기엔 좀 어려운 유형이라고 한다. 타임머신이라는 주제부터가 그렇다.

코드

#include <iostream>
#include <vector>
using namespace std;

const int INF = 0x7FFFFFFF;
int N, M; 
vector< pair<int, int> > graph[501];
int res[501];

int main() {
    cin >> N >> M;
    int a, b, c;
    for (int i = 0; i < M; i++) {
        cin >> a >> b >> c;
        graph[a].push_back({ b,c });
    }
    for (int i = 1; i <= N; i++) {
        res[i] = INF;
    }
    res[1] = 0; //처음 시작할 정점 

    bool check = false;
    //각 노드마다 모든 엣지에 대해 Relax
    for (int i = 1; i <= N; i++) { 
        for (int j = 1; j <= N; j++) { 
            for (int k = 0; k < graph[j].size(); k++) {
                int nextV = graph[j][k].first;
                int nextCost = graph[j][k].second;
                if ((res[j] != INF) && (res[nextV] > res[j] + nextCost)) {
                    res[nextV] = res[j] + nextCost;
                    if (i == N) { //N-1까지 돌고 N번째에서 값이 갱신되면 음수 싸이클
                        check = true;
                        break;
                    }
                }
            }
        }
    }

    if (check) cout << "-1\n";
    else {
        for (int i = 2; i <= N; i++) {
            if (res[i] == INF) cout << "-1\n";
            else cout << res[i] << "\n";
        }
    }
    return 0;
}

출처

예비개발자님 블로그
Ries 마법의 슈퍼마리오님 블로그
https://roeniss.tistory.com