핵심 요약

음수 간선이 있는 그래프에서 최단경로를 구하거나 음수 사이클 존재 여부를 판단할 때 쓴다. 다익스트라가 안 되는 상황에서 꺼내는 카드.

개념 설명

벨만-포드 알고리즘

다익스트라는 매 단계에서 현재 가장 가까운 노드를 선택해 탐색한다. 덕분에 빠르지만, 음수 간선이 있으면 이미 “확정”된 노드가 나중에 더 짧은 경로로 도달될 수 있어서 틀린 답을 낸다.

벨만-포드는 반대로 매 라운드마다 모든 간선을 전부 확인하며 dist를 갱신한다. 느리지만(O(VE)) 음수 간선도 처리할 수 있다.

작동 원리: N개의 정점을 잊는 단순 경로에는 최대 N-1개의 간선이 존재한다. 따라서 모든 간선을 N-1번 확인하면 모든 최단경로가 확정된다.

언제 쓰나?

  • 그래프에 음수 가중치 간선이 포함된 경우
  • 음수 사이클 존재 여부를 확인해야 하는 경우
  • 시작점이 정해지지 않아 “어느 경로에서든” 사이클 확인이 필요한 경우

핵심 패턴 (C++)

1
2
3
4
5
6
7
8
9
10
11

vector<int> dist(n+1, INF);
dist[start] = 0;

for (int i = 0; i < n; i++) {
    for (auto& e : edges) {
        if (dist[e.u] != INF && dist[e.v] > dist[e.u] + e.cost) {
            dist[e.v] = dist[e.u] + e.cost;
            if (i == n-1) { /* 음수 사이클 */ }
        }
    }
}

음수 사이클 감지 원리

N-1번 반복으로 최단경로가 이미 확정됐다면, N번째 라운드에서는 어떤 dist도 갱신되면 안 된다. 만약 갱신된다면? 그 경로 어딘가에 계속 돌수록 비용이 줄어드는 음수 사이클이 존재한다는 뜻이다.

이 문제에서의 적용

BOJ 1865 웜홀에서 어떻게 썼나?

이 문제의 핵심 관찰은 두 가지다:

  1. “시작점이 지정되지 않는다” — 어느 지점에서 출발해도 시간이 역행하는 경로가 있으면 YES다. 따라서 특정 시작점에서 벨만-포드를 돌리는 게 아니라, 모든 정점을 시작점으로 간주해야 한다. 이를 구현하는 가장 쉬운 방법이 dist를 INF가 아닌 0으로 초기화하는 것이다 — 마치 모든 점에서 동시에 시작하는 것처럼.
  2. 도로는 양방향, 웜홀은 단방향 음수 — 도로는 edges에 양방향으로 두 번 추가, 웜홀은 -cost로 단방향 추가.
1
2
3
4
5
6
7
8
9
10
11
12

// dist를 0으로 초기화 = 모든 정점에서 동시 출발 효과
vector<int> dist(n+1, 0);
bool cycle = false;

for (int i = 0; i < n; i++) {
    for (auto& e : edges) {
        if (dist[e.v] > dist[e.u] + e.cost) {
            dist[e.v] = dist[e.u] + e.cost;
            if (i == n-1) cycle = true;
        }
    }
}

INF 체크 없애는 이유: 일반 벨만-포드에선 dist[u] != INF 조건을 달지만, 웜홀은 dist가 모두 0이라 INF인 노드가 없다. 오히려 INF 조건을 달면 연결되지 않은 컴포넌트의 음수 사이클을 못 잡는 반례가 생긴다.

주의할 점 / 흔한 실수

  • dist INF 초기화 vs 0 초기화: 단일 출발점 최단경로 → INF 초기화. 전체 그래프 음수 사이클 감지 → 0 초기화. 헷갈리지 말 것.
  • INF 체크 조건 누락/추가 오류: 웜홀체럼 dist를 0으로 초기화하면 INF 비교 조건이 필요 없다. 반대로 INF 초기화 문제에서 INF 체크 빼면 오버플로우 발생.
  • 오버플로우: N=500, E=6000, cost=-10000이면 최악 누적값이 int 범위를 초과할 수 있다. 필요시 long long 사용.
  • 사이클 감지 시 N vs N+1번 반복: N번 돌면서 i==N-1일 때 갱신 체크하는 방식과, N-1번 돌고 한 번 더 검사하는 방식 둘 다 동일하다.
  • 무방향 그래프: 도로 같은 무방향 간선은 반드시 양방향으로 두 번 추가.

이런 패턴이면 벨만-포드를 의심하라

문제를 보자마자 벨만-포드를 떠올려야 하는 시그널들:

키워드/조건 시그널

  • “음수 가중치”가 명시된 그래프에서 최단거리 구하기
  • “시간이 거꾸로 간다”, “비용이 줄어든다”, “웜홀” 같은 표현
  • “음수 사이클이 존재하는지 판단하라”
  • “출발점에서 다시 출발점으로 돌아왔을 때 값이 줄어드는가”
  • 시작점이 고정되지 않고 “어느 지점에서 출발해도” 성립하는지

구조적 시그널

  • 간선 가중치에 음수가 포함될 수 있다 (문제에서 명시하거나, 값 범위에 음수 포함)
  • 무방향 그래프 + 웜홀(단방향 음수 간선)이 섞여 있음
  • 정점 수 N이 500 이하, 간선 수 E가 수천 이하 → O(VE) 허용 범위
  • 플로이드-워셜은 N이 너무 크거나(N>500), 단일 출발 최단경로만 필요할 때 벨만-포드 선택

다익스트라 vs 벨만-포드 즉시 판단 기준

상황 선택
음수 간선 없음 다익스트라
음수 간선 있음, 사이클 감지 불필요 벨만-포드 또는 SPFA
음수 사이클 존재 여부 확인 필요 벨만-포드 (필수)
전체 쌍 최단거리, N ≤ 500 플로이드-워셜

자료구조와 코드 라인별 분석

어떤 자료구조에 담나?

벨만-포드는 간선 중심 알고리즘이다. 다익스트라처럼 인접 리스트(노드 기준)가 아니라, 간선 리스트(Edge list) 로 저장해야 한다.

1
2

struct Edge { int u, v, cost; };  // 출발 → 도착, 가중치
vector<Edge> edges;               // 모든 간선을 평탄하게 저장

인접 리스트(vector<vector<pair<int,int>>>)로도 구현할 수 있지만, 모든 간선을 순회할 때 중첩 루프가 필요해서 코드가 지저분해진다. 간선 리스트가 훨씬 깔끔하다.

dist 배열은 1차원 vector<int> 또는 vector<long long>.

핵심 패턴 라인별 분석

1
2
3

// ① dist 초기화
vector<int> dist(n+1, 0);  // [웜홀형] 시작점 불명 → 전부 0
// vector<int> dist(n+1, INF); dist[start] = 0;  // [일반형] 단일 출발점
  • 0 초기화: 모든 정점을 동시에 출발점으로 간주. “어느 정점에서 출발해도” 음수 사이클이 있으면 잡힌다.
  • INF 초기화: 특정 출발점에서의 최단거리를 구할 때. 방문 안 된 노드는 갱신 대상에서 제외(dist[u] != INF 체크 필요).
1
2

// ② 외부 루프: N번 (또는 N-1번 + 1번 추가 검사)
for (int i = 0; i < n; i++) {
  • N-1번이면 최단경로 확정, N번째는 사이클 감지용.
  • i < n으로 N번 돌면서 i == n-1일 때 갱신되면 사이클 존재. 깔끔한 패턴.
1
2

// ③ 내부 루프: 모든 간선 순회
for (auto& e : edges) {
  • 다익스트라와의 핵심 차이. 다익스트라는 연결된 간선만 보지만, 벨만-포드는 매 라운드 전체 간선을 본다.
  • 덕분에 음수 간선이 있어도 틀리지 않는다. 어떤 순서로 처리해도 N-1번 후엔 수렴이 보장된다.
1
2
3

// ④ Relaxation (완화)
if (dist[e.v] > dist[e.u] + e.cost) {
    dist[e.v] = dist[e.u] + e.cost;
  • 핵심 연산. “u를 거쳐 v로 가는 게 현재 v까지의 비용보다 싸면 갱신”.
  • INF 초기화 버전에서는 앞에 dist[e.u] != INF && 조건 추가 필수. 안 달면 INF + cost가 오버플로우.
1
2

// ⑤ 음수 사이클 감지
    if (i == n-1) cycle = true;
  • N-1번으로 모든 경로가 확정됐는데도 N번째 라운드에서 갱신이 일어남 = 무한히 줄어드는 사이클 존재.

변형 포인트

변형 1 — 출발점 있음 (일반 최단거리)

1
2
3

vector<long long> dist(n+1, INF);
dist[start] = 0;
// 내부: if (dist[e.u] != INF && dist[e.v] > dist[e.u] + e.cost)

변형 2 — 음수 사이클 노드에서 도달 가능한 모든 노드 처리

1
2

// N번째 라운드에서 갱신된 노드를 BFS/DFS로 펼쳐서
// 도달 가능한 모든 노드를 -INF로 마킹

변형 3 — SPFA (큐 최적화)

1
2
3
4

queue<int> q;
vector<bool> inQueue(n+1, false);
// 갱신된 노드만 큐에 넣어서 다음 라운드에 처리
// 평균 O(E), 최악 O(VE)로 같지만 보통 훨씬 빠름

변형 4 — 최장 경로 (부호 반전)

  • 모든 간선 cost를 -cost로 바꾸고 최단경로 → 최장경로 변환
  • 단, 양수 사이클(원래 음수 사이클)이 생기면 무한대 주의

추가로 알면 좋은 것

  • SPFA (Shortest Path Faster Algorithm): 벨만-포드를 큐로 최적화한 버전. 평균적으로 더 빠르지만 최악은 동일. 음수 사이클 감지에도 사용 가능.
  • 플로이드-워셜: 모든 쌍 최단경로 필요 시 O(V³). N이 작을 때(≤500)는 웜홀처럼 플로이드도 고려 가능.
  • 알고리즘 선택 기준: 음수 간선 없으면 다익스트라(O(ElogV)), 음수 간선 있거나 사이클 감지 필요하면 벨만-포드(O(VE)).

연관 문제 추천

  • BOJ 11657 스타보 지하철 — 기본 벨만-포드 + 음수 사이클로 도달 불가 정점 처리
  • BOJ 1219 오민식의 고민 — 음수 사이클 노드에서 도달 가능한 모든 노드 처리