[BOJ알고리즘, C++]#11657_타임 머신, 길 찾기, 최단 경로 알고리즘, 벨만-포드, 음수 가중치, 음수 사이클

 

#1. 문제

11657번: 타임머신

 

---

 

#2. 풀이

 

1. 벨만-포드

[알고리즘]#2_길 찾기 알고리즘

 

벨만-포드 알고리즘은 음수 가중치를 포함하는 가중치 그래프 내 '단일-출발' 혹은 '단일-쌍' 최단 경로 값을 찾는 길 찾기 알고리즘입니다. 벨만-포드 알고리즘은 그래프 내 사이클 형성과 동시에 해당 경로에 존재하는 간선들의 가중치의 합이 음수가 되는 '음수 사이클'을 탐지하는 보조적인 작업을 병행합니다. 벨만-포드 알고리즘은 간선 중심의 최단 경로 알고리즘으로, N-1번 간선 목록을 순회하며 최단 경로 값을 경신한 후, 마지막 한 번 간선 목록을 순회하며 최단 경로 값의 갱신 여부를 통해 '음수 사이클'을 탐지합니다.

 

2. 타임 머신은 '음수 가중치'를 갖는 간선이다!

1. 간서 목록을 구성합니다.
2. 벨만-포드 알고리즘을 수행하며 음수 사이클이 탐지되면 -1을 출력하고, 그렇지 않다면 정상적으로 각 정점의 최단 경로 값을 출력합니다.

 

---

#3. 코드

 

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

struct Edge {
    int from, to, cost;
    Edge(int u, int v, int c) : from(u), to(v), cost(c) {}
};

const int INF = 1e9;
int N, M;
vector<long long> dist;
vector<Edge> edges;

bool bellman_ford() {
    dist[1] = 0;
    for (int i = 1; i <= N; i++) {
        for (Edge &e : edges) {
            if (dist[e.from] == INF) continue;
            if (dist[e.to] > dist[e.from] + e.cost) {
                dist[e.to] = dist[e.from] + e.cost;
                if (i == N) return true; // negative cycle detected
            }
        }
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;
    dist = vector<long long>(N + 1, INF);
    for (int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        edges.push_back(Edge(a, b, c));
    }

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

    return 0;
}

 

---