벨만-포드 알고리즘 (Bellman-Ford Algorithm)

정의

벨만-포드 알고리즘 (Bellman-Ford Algorithm) 은 음수 가중치 간선을 허용하면서 단일 시작점 s 로부터 모든 정점까지의 최단 거리를 찾는 DP 기반 알고리즘. Richard Bellman (1958) 과 Lester Ford Jr. (1956) 가 독립적으로 발표. 음수 사이클 검출 기능 내장. 시간 복잡도 O(VE).

문제 상황과 동기

그래프에 음수 가중치 간선이 있을 수 있다. 시작점 s 에서 모든 정점까지 최단 거리를 구하고, 음수 사이클 존재 여부도 판정하고 싶다.

• Dijkstra: 음수 간선이 하나라도 있으면 틀림. 확정된 정점의 거리가 나중에 더 짧아질 수 있기 때문.
• BFS: 가중치가 모두 1일 때만 O(V + E). 가중치 다르면 불가.
• Bellman-Ford: 음수 가중치 OK, 음수 사이클 검출 OK. O(VE). 간선 많으면 느리지만 유일한 선택.

핵심 통찰: V-1 번 간선 완화 (relax) 를 반복하면, 최단 경로 (최대 V-1 개 간선) 에 대한 dist 가 수렴. V 번째에도 갱신되면 음수 사이클 존재.

시각화

핵심 아이디어

invariant: k번째 반복 후 dist[v] = s 에서 v 까지 최대 k 간선 사용 최단 거리. 최단 경로는 최대 V-1 간선이므로 V-1 번 반복하면 수렴.

relax(u, v, w):
    if dist[u] + w < dist[v]:
        dist[v] = dist[u] + w

모든 간선을 V-1 번 relax. 순서 무관. DP의 한 형태.

음수 사이클 검출: V-1 번 후 한 번 더 (V번째) 완화해서 dist 가 변하면 음수 사이클 존재.

알고리즘

BellmanFord(G, s):
    dist[s] = 0, dist[v!=s] = ∞

    for i = 1 to V-1:                  // V-1 번 반복
        for each edge (u, v, w):
            if dist[u] != ∞ and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    // 음수 사이클 검출
    for each edge (u, v, w):
        if dist[u] != ∞ and dist[u] + w < dist[v]:
            return "negative cycle detected"
    
    return dist

구현

// O(VE) Bellman-Ford + 음수 사이클 검출
#include <bits/stdc++.h>
using namespace std;
struct Edge { int u, v, w; };
​
int main() {
  int n, m, s;
  cin >> n >> m >> s;         // n 정점, m 간선, s 시작점 (1-indexed)
  vector<Edge> edges(m);
  for (auto& e : edges) cin >> e.u >> e.v >> e.w;
​
  vector<long long> dist(n + 1, 1e18);
  dist[s] = 0;
​
  // V-1 번 완화
  for (int i = 0; i < n - 1; i++) {
      for (auto [u, v, w] : edges) {
          if (dist[u] != 1e18 && dist[u] + w < dist[v])
              dist[v] = dist[u] + w;
      }
  }
​
  // 음수 사이클 검출
  bool negCycle = false;
  for (auto [u, v, w] : edges) {
      if (dist[u] != 1e18 && dist[u] + w < dist[v]) {
          negCycle = true;
          break;
      }
  }
​
  if (negCycle) {
      cout << "NEGATIVE CYCLE\n";
  } else {
      for (int i = 1; i <= n; i++)
          cout << (dist[i] == 1e18 ? -1 : dist[i]) << " ";
  }
}

# O(VE) Bellman-Ford
import sys
input = sys.stdin.readline
INF = int(1e18)
​
n, m, s = map(int, input().split())
edges = []
for _ in range(m):
  u, v, w = map(int, input().split())
  edges.append((u, v, w))
​
dist = [INF] * (n + 1)
dist[s] = 0
​
for _ in range(n - 1):
  for u, v, w in edges:
      if dist[u] != INF and dist[u] + w < dist[v]:
          dist[v] = dist[u] + w
​
# 음수 사이클 검출
neg_cycle = False
for u, v, w in edges:
  if dist[u] != INF and dist[u] + w < dist[v]:
      neg_cycle = True
      break
​
if neg_cycle:
  print("NEGATIVE CYCLE")
else:
  print(' '.join(str(-1 if dist[i] == INF else dist[i]) for i in range(1, n + 1)))

// Bellman-Ford + 음수 사이클
import java.util.*;
import java.io.*;
public class Main {
  static class Edge { int u, v, w; Edge(int u, int v, int w) { this.u=u; this.v=v; this.w=w; }}
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      int n = Integer.parseInt(st.nextToken());
      int m = Integer.parseInt(st.nextToken());
      int s = Integer.parseInt(st.nextToken());
      
      Edge[] edges = new Edge[m];
      for (int i = 0; i < m; i++) {
          st = new StringTokenizer(br.readLine());
          int u = Integer.parseInt(st.nextToken());
          int v = Integer.parseInt(st.nextToken());
          int w = Integer.parseInt(st.nextToken());
          edges[i] = new Edge(u, v, w);
      }
      
      long INF = (long)1e18;
      long[] dist = new long[n + 1];
      Arrays.fill(dist, INF);
      dist[s] = 0;
      
      for (int i = 0; i < n - 1; i++) {
          for (Edge e : edges) {
              if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v])
                  dist[e.v] = dist[e.u] + e.w;
          }
      }
      
      boolean negCycle = false;
      for (Edge e : edges) {
          if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v]) {
              negCycle = true;
              break;
          }
      }
      
      if (negCycle) {
          System.out.println("NEGATIVE CYCLE");
      } else {
          StringBuilder sb = new StringBuilder();
          for (int i = 1; i <= n; i++)
              sb.append(dist[i] == INF ? -1 : dist[i]).append(' ');
          System.out.println(sb);
      }
  }
}

5 6 1
1 2 4
1 3 3
2 3 -2
3 4 1
2 4 5
4 5 2

0 4 2 3 5

3 3 1
1 2 1
2 3 -3
3 1 1

NEGATIVE CYCLE

복잡도

Dijkstra 보다 느리지만 음수 간선 필수 상황에서 유일한 선택.

증명 스케치

귀납법: k번째 반복 후 dist[v] 는 s 에서 v 까지 최대 k 간선 사용 최단 거리.

• Base: k=0, dist[s]=0, 나머지 ∞.
• Step: k번째까지 dist[u] 정확하다 가정. k+1번째에 (u, v, w) 완화하면 dist[v] 는 k+1 간선 최단.
• 최단 경로는 사이클 없으므로 최대 V-1 간선. V-1 번 반복하면 모든 dist 수렴.

음수 사이클: V번째 완화에서 dist 변하면, V 개 간선 사용 경로가 V-1 개 간선보다 짧다. 사이클 존재 + 음수 가중치 합.

SPFA (Shortest Path Faster Algorithm)

Bellman-Ford 의 큐 최적화. 매번 모든 간선 안 보고, dist 변한 정점의 이웃만 완화.

SPFA(G, s):
    dist[s] = 0, dist[v!=s] = ∞
    queue = [s], inQueue[s] = true

    while queue not empty:
        u = queue.pop()
        inQueue[u] = false
        for (v, w) in neighbors(u):
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                if not inQueue[v]:
                    queue.push(v)
                    inQueue[v] = true

평균 O(E), 최악 O(VE) (음수 사이클 근처). PS에서 Bellman-Ford 보다 빠른 경우 많음.

변형 / 활용

함정

1. INF 체크 안 함

dist[u] != INF 체크 안 하면 overflow. u 도달 불가인데 완화하면 쓰레기 값 전파.

2. V-1 번 vs V 번 혼동

V-1 번 완화가 최단 경로 계산. V 번째는 음수 사이클 검출 전용.

3. 음수 사이클 있어도 일부 정점 거리 정확

음수 사이클에 도달 불가능한 정점은 dist 정확. 음수 사이클 영향 받는 정점만 -∞.

4. SPFA queue size 폭발

음수 사이클 있으면 같은 정점이 큐에 계속 들어감. visit count 배열로 V번 이상 들어가면 음수 사이클 판정.

5. long long vs int

dist 초기값 1e18, 간선 가중치 합 오버플로우. C++ 에서 long long 필수.

BOJ 연습 문제

참고

• 다익스트라 알고리즘
• 플로이드-워셜
• Shortest Path Faster Algorithm