(c++) 벨만-포드 알고리즘 11657번: 타임머신

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

11657번: 타임머신

 

 

---

 

 

벨만-포드 알고리즘

 

앞선 다익스트라 알고리즘은 기본적으로 음수의 가중치가 없다는 것을 가정한다.

 

음수 값으로 나오는 사이클을 만난다면 사이클을 돌 때마다 최솟값을 갱신하기 때문이다.

 

이번에 볼 알고리즘은 위 경우를 해결하고, 최단 경로도 도출할 수 있다.

 

벨만-포드 알고리즘은 최단 거리의 특성을 이용하여 알고리즘을 구성한다.

 

시작점에서 u와 v까지의 최단거리 dist[u], dist[v]에 대해서 

 

dist[v] ≤ dist[u] + w(u, v)

위 식을 항상 만족하게 된다.

 

시작점 → u → v 

w(u, v) = 10, dist[u] = 10, dist[v] = 30 이라고 가정한다면

시작점에서 u까지 10의 최단 거리가 있고, 시작점에서 v까지 30이라는 최단 거리가 있다면

 

dist[u] 에서 u →v 10만 더해도 20이라는 거리가 나오는데 dist[v]가 이것보단 무조건 같거나 작을 것이다.

 

30 ≤10 + 10 (모순이다.)

 

즉 dist[v]의 최대가 dist[u] + w(u, v)가 된다. 

위 작업을 완화라고 하며, 벨만-포드 알고리즘은 모든 간선에 대해서 완화 작업을 하게 된다.

 

그럼 음수 사이클에 대해서는 어떻게 알 수 있을까?

 

정점의 시작점에서 끝점까지 최단 경로에서의 간선의 수는 당연히 정점 - 1이다.

그런데 음수 사이클을 만났다면 간선을 정점 - 1보단 더 지나갔다는 의미가 된다.

 

그래서 모든 간선에 대해서 정점의 수 V -1번 완화 작업을 반복하면 시작점에서 최단 거리를 알 수 있고

 

V번 째 완화 작업이 된다는 것은 음수 사이클이 존재하단 의미가 된다.

 

이제 코드로 보자

 

 

11657번: 타임머신

 

 

#include <bits/stdc++.h>
#define INF 1e9
using namespace std;
// N = 도시 수, M = 버스 노선 수 
int N, M;

vector<pair<int, int> > graph[501];

vector<long long> bellman(int start) {
    vector<long long> upper(N+1, INF);
    upper[start] = 0;
    bool updated;
    // N번 순회
    for(int iter = 1; iter <= N; iter++) {
        updated = false;
        for (int here = 1; here <= N; here++) {
            for (int i = 0; i < graph[here].size(); i++) {
                int there = graph[here][i].first;
                int cost = graph[here][i].second;
                //완화
                if (upper[here] != INF && upper[there] > upper[here] + cost) {
                    upper[there] = upper[here] + cost;
                    updated = true;
                }
            }
        }
    }
    // N번 째에도 완화가 된다면 음수 사이클 존재
    if (updated) upper[0] = -1;
    return upper;
}

int main(void) {
    cin >> N >> M;
    // 버스 노선 정보
    for (int i = 0; i < M; i++) {
        int A, B, C;
        cin >> A >> B >> C;
        graph[A].push_back({B, C});
    }
    vector<long long> result;
    result = bellman(1);
    if (result[0] == -1) {
        cout << -1;
    } else {
        for (int i = 2; i <= N; i++) {
            if (result[i] < INF - 100) {
                cout << result[i];
            } else {
                cout << -1;
            }
            cout << '\n';
        }
    }
}

 

N번 반복을 수행하는데 반복문이 시작되는 상단에

updated 값을 false로 초기화하고, 완화가 된다면 true로 바꾸게 했다.

 

만약 N번째에 완화가 성공하고 반복문을 빠져나온다면 updated는 true가 될 것이다.

그 경우에 사용하지 않는 upper 배열의 0번째에 -1을 주어 판별하게 했다. (이렇게 안해도 된다.)

 

최단 경로 값을 저장하는 upper 배열은 long long으로 주는 것이 좋은데

최대로 나올 수 있는 값이 무척 크고 INF로 선언한 값이 작더라도 int보다 커질 수 있기 때문이다.