벨만-포드

어떤 문제를 푸는가

다익스트라는 음수 간선 이 있으면 틀립니다. 벨만-포드는 음수 가중치 간선이
있어도 단일 시작점 최단 경로를 구하고, 나아가 음수 사이클 의 존재까지
탐지합니다.

핵심 아이디어 — 모든 간선을 V−1번 이완

최단 경로는 사이클을 포함하지 않으므로 간선을 최대 \(V-1\)개 거칩니다.
따라서 모든 간선에 대한 이완을 \(V-1\)번 반복하면 모든 최단 거리가 확정됩니다.

$$ \text{매 라운드: 모든 } (u, v, w)\text{에 대해 } dist[v] \leftarrow \min(dist[v],\ dist[u] + w) $$

왜 V−1번이면 충분한가

귀납적으로 봅니다. \(k\)번째 라운드가 끝나면, 간선을 최대 \(k\)개 쓰는 모든
최단 경로가 dist에 반영됩니다. 시작점에서 임의 정점까지의 최단 경로가
간선을 \(\ell\)개 쓴다면, \(\ell\)번째 라운드에 그 거리가 확정됩니다. 단순 경로의
간선 수는 최대 \(V-1\)이므로 \(V-1\)번이면 모두 끝납니다.

핵심은 라운드 안에서 모든 간선을 빠짐없이 본다는 점입니다. 순서는 상관없고,
한 라운드에서 운 좋게 더 멀리 갱신될 수도 있지만 최악의 경우를 \(V-1\)로 잡습니다.

음수 사이클 탐지

\(V-1\)번 이완 뒤에도 여전히 갱신되는 간선 이 있다면, 그 경로는 사이클로
무한히 줄어드는 음수 사이클을 포함합니다. \(V\)번째 라운드에서 한 번 더 돌려
갱신 여부를 확인하면 됩니다.

음수 사이클이 있으면 "최단 경로"는 \(-\infty\)로 정의되지 않으므로, 보통은
"음수 사이클 존재"만 보고합니다.

복잡도

다익스트라의 \(O(E \log V)\)보다 느립니다. 그러니 음수 간선이 없으면
다익스트라, 음수가 있거나 음수 사이클 판정이 필요하면 벨만-포드를 씁니다.

다익스트라와의 비교

다음 강의에서 구현, 음수 사이클 보고, 그리고 큐로 가속하는 SPFA를 봅니다.

표준 구현 (C++)

간선 리스트만 있으면 됩니다. 인접 리스트도 필요 없습니다.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;

struct Edge { int u, v; ll w; };

int main() {
    int n, m; cin >> n >> m;
    vector<Edge> edges(m);
    for (auto& e : edges) cin >> e.u >> e.v >> e.w;

    vector<ll> dist(n + 1, INF);
    dist[1] = 0;                          // 시작점 1

    bool negcycle = false;
    for (int i = 1; i <= n; i++) {        // n번째에서 사이클 탐지
        for (auto& e : edges) {
            if (dist[e.u] == INF) continue;        // 도달 못한 정점은 건너뛴다
            if (dist[e.u] + e.w < dist[e.v]) {
                dist[e.v] = dist[e.u] + e.w;
                if (i == n) negcycle = true;       // V번째에도 갱신 → 음수 사이클
            }
        }
    }

    if (negcycle) { cout << -1 << '\n'; return 0; }
    for (int v = 2; v <= n; v++)
        cout << (dist[v] == INF ? -1 : dist[v]) << '\n';
}

핵심 두 줄:

• if (dist[e.u] == INF) continue; — 도달 못한 정점에서의 이완 금지.
  이걸 빼면 INF + (음수)가 더 작아져 엉뚱한 정점이 음수로 갱신됩니다.
• if (i == n) — \(V-1\)라운드까지가 본 계산, \(V\)번째 라운드의 갱신은
  음수 사이클 신호입니다.

특정 시작점에서 도달 가능한 음수 사이클만

문제에 따라 "시작점에서 갈 수 있는 음수 사이클"만 의미가 있습니다. 그러면
시작점에서 도달 가능한 정점만 고려하거나, \(V\)번째 갱신된 정점에서 역방향
BFS로 시작점에 영향을 주는지 확인합니다.

SPFA — 큐로 가속한 벨만-포드

매 라운드 모든 간선을 보는 대신, 거리가 바뀐 정점만 큐에 넣어 그 이웃을
이완합니다. 평균적으로 빠르지만 최악은 여전히 \(O(VE)\)입니다.

queue<int> q;
vector<int> inq(n + 1, 0), cnt(n + 1, 0);
dist[s] = 0; q.push(s); inq[s] = 1;
while (!q.empty()) {
    int u = q.front(); q.pop(); inq[u] = 0;
    for (auto [v, w] : adj[u]) {
        if (dist[u] + w < dist[v]) {
            dist[v] = dist[u] + w;
            if (++cnt[v] >= n) { /* 음수 사이클 */ }
            if (!inq[v]) { q.push(v); inq[v] = 1; }
        }
    }
}

cnt[v] >= n(어떤 정점이 \(n\)번 이상 큐에 들어감)이면 음수 사이클입니다.

흔한 함정

• 도달 불가 정점 이완 — 위에서 강조한 INF 체크 누락. 가장 자주 틀립니다.
• INF 덧셈 오버플로 — INF를 INT_MAX로 잡고 음수를 더하면 넘칩니다.
  long long과 넉넉한 INF(1e18)를 쓰되, 도달 불가는 더하지 않기.
• 무방향 음수 간선 — 무방향 그래프에서 음수 간선은 곧 음수 사이클입니다.

응용 패턴

• 시간/환율 차익(arbitrage) — 곱셈을 로그로 바꿔 합으로, 음수 사이클 = 차익.
• 차분 제약 시스템 — \(x_j - x_i \le c\) 형태의 부등식들을 간선으로 보고
  벨만-포드로 해의 존재성(음수 사이클 = 무해)과 한 해를 구합니다.

음수가 끼어들면 다익스트라의 "한 번 확정"이 무너진다는 점, 그래서 "모든 간선을
반복해서 이완"으로 돌아간다는 점이 이 단원의 본질입니다.

출제 신호

벨만-포드를 골라야 하는 순간은 명확합니다.

• 최단 경로 문제인데 간선 가중치가 음수일 수 있음 — "시간이 줄어드는
  웜홀", "비용이 환급되는 경로" 같은 서사가 단서입니다.
• "음수 사이클(시간 역행, 무한히 이득)이 존재하는지 판정하라"
• 제약 신호: \(V \le 500\), \(E \le 6000\) 정도의 작은 그래프 — \(O(VE)\)가
  허용되는 크기라는 뜻 자체가 벨만-포드 신호입니다.
• 변형 신호: "간선을 정확히/최대 \(k\)개만 써서 최단 경로" — 이완 횟수를
  제한하는 벨만-포드 변형(라운드별 스냅숏)입니다.

음수 간선이 없다면 같은 문제를 다익스트라로 더 빠르게 풉니다. 벨만-포드는
"음수 간선 또는 이완 횟수 제한"이라는 조건이 있을 때만 꺼내는 도구입니다.

풀이 결정 절차

1. 음수 간선 유무를 제약에서 확인합니다. 있다면 다익스트라는 탈락.
2. \(V \times E\)를 계산해 \(10^8\) 안쪽인지 검산합니다.
3. 문제가 묻는 것을 구분합니다 — (a) 최단 거리, (b) 음수 사이클 존재 여부,
   © 음수 사이클의 영향을 받는 정점 판별. ©는 \(V\)번째 라운드에서
   갱신된 정점으로부터 도달 가능한 모든 정점을 추가로 퍼뜨려야 합니다.
4. 거리 자료형 — 음수 누적까지 고려해 long long이 기본입니다.

자주 하는 실수

가장 치명적인 버그는 INF 정점에서의 이완입니다. 아직 도달하지 못한
정점(\(\text{dist}=\infty\))에서 음수 간선을 이완하면 \(\infty + (-w)\)라는
가짜 거리가 전파되고, C++에선 오버플로로 음수가 되어 그래프 전체가 오염됩니다.

for (int round = 0; round < n - 1; round++)
    for (auto [u, v, w] : edges) {
        if (dist[u] == INF) continue;      // 이 줄이 없으면 INF-오염 + 오버플로
        dist[v] = min(dist[v], dist[u] + w);
    }

• 사이클 판정 라운드 누락 — \(V-1\)라운드로 거리는 수렴하지만, 음수 사이클
  판정은 한 라운드 더(\(V\)번째) 돌려서 여전히 갱신되는지 봐야 합니다.
• "시작점에서 도달 가능한" 사이클만 인정해야 하는 문제 — 그래프 어딘가의
  음수 사이클과 시작점에서 닿는 음수 사이클은 다릅니다. 도달 불가 정점에서의
  갱신을 사이클로 오인하지 않도록 위의 INF continue가 여기서도 핵심입니다.
• 조기 종료 최적화의 오해 — 한 라운드 동안 갱신이 전혀 없으면 즉시 끝내도
  됩니다. 이 플래그를 음수 사이클 판정과 혼동해 거꾸로 쓰는 실수가 있습니다.

for r in range(n):                       # n 라운드: 마지막 라운드는 판정용
    updated = False
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
            updated = True
            if r == n - 1:               # V번째 라운드에도 갱신 → 음수 사이클
                has_negative_cycle = True
    if not updated:
        break

연습 방법

사이드바 연습 목록의 기본 음수 간선 최단 경로(웜홀류)로 표준 구현과 사이클
판정을 익히고, "도달 가능한 사이클만" 따지는 변형, 간선 개수 제한 변형 순서로
확장하세요. 매 문제에서 "INF 스킵을 넣었는가, \(V\)번째 라운드를 돌렸는가,
long long인가"를 점검하면 벨만-포드 오답의 90%는 사라집니다. 태그된 문제
3문제 이상 해결 시 마스터 처리되어 레이팅 CLASS 보너스에 반영됩니다.