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

벨만-포드 알고리즘(Bellman-Ford Algorithm)은 음의 가중치를 허용하는 최단 경로 찾기 알고리즘입니다.

다익스트라 알고리즘과 달리 음의 가중치가 있어도 동작하지만, 음의 사이클(negative weight cycle)이 존재할 경우 경로를 제대로 계산할 수 없습니다.

이 알고리즘은 단일 시작점에서 다른 모든 정점까지의 최단 거리를 구할 수 있습니다.

Table of Contents

벨만-포드 알고리즘 예제

주요 코드:

function bellmanFord(edges, V, source) {
    // 거리 배열 초기화
    const dist = Array(V).fill(Infinity);
    dist[source] = 0;

    // V - 1번 간선 Relaxation 반복
    for (let i = 0; i < V - 1; i++) {
        for (const [u, v, w] of edges) {
            if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
    }

    // 음의 사이클 존재 여부 확인
    for (const [u, v, w] of edges) {
        if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
            console.log("Negative weight cycle detected");

            return null;
        }
    }

    return dist;
}

사용 예제:

// 그래프의 간선 리스트: [출발, 도착, 가중치]
const edges = [
    [0, 1, 4],
    [0, 2, 5],
    [1, 2, -3],
    [2, 3, 4],
    [3, 1, -6]
];

const V = 4; // 정점 수
const source = 0;
const result = bellmanFord(edges, V, source);

if (result !== null) {
    console.log("Shortest distances from source:", result);
}

출력 결과:

Negative weight cycle detected

// OR 음의 사이클이 없는 경우

Shortest distances from source: [0, -6, -4, 0]

개요

입력: 가중치가 있는 방향을 가진 그래프 G(V, E)
출력: 시작 정점으로부터 모든 정점까지의 최단 거리
복잡도: O(V × E)
특징:
- 음의 가중치를 가지는 간선 허용
- 음의 사이클 탐지 가능
- 느리지만 일반적인 그래프에 적용 가능

용어 정리

Relaxation: 더 짧은 경로 발견 시 거리 갱신
음의 사이클: 무한히 비용을 줄일 수 있는 사이클로 벨만-포드로 탐지 가능
최단 경로의 간선 수는 V-1 이하

핵심 아이디어

최단 경로는 최대 V-1개의 간선으로 구성된다.
- 왜냐하면 사이클이 없다고 가정하면 경로 상의 정점 수는 V 이하이므로 간선 수는 V-1 이하
그래프의 모든 간선을 V-1번 반복하면서 relax 연산을 수행한다.
- relax(u, v)는 u에서 v로 가는 더 짧은 경로가 발견되었을 때 v의 거리를 갱신하는 것.

벨만-포드 알고리즘 단계

초기화
- 시작 정점 s의 거리를 0으로, 나머지 정점의 거리를 무한대로 설정
V-1번 간선 Relaxation 반복
- 그래프의 모든 간선을 하나씩 확인하여 u → v 경로를 업데이트
음의 사이클 존재 확인
- 모든 간선을 한 번 더 확인했을 때 갱신되는 값이 있으면, 음의 사이클 존재

예제

입력 그래프

정점: A(시작점), B, C, D
간선:
A → B (4)
A → C (5)
B → C (-3)
C → D (4)
D → B (-6)

1 단계: 초기화

dist[A] = 0, dist[B] = ∞, dist[C] = ∞, dist[D] = ∞

2단계: Relaxation 수행 (V-1 = 3번)

1회차:

A→B: dist[B] = min(∞, 0+4) → 4
A→C: dist[C] = min(∞, 0+5) → 5
B→C: dist[C] = min(5, 4 + (-3)) → 1
C→D: dist[D] = min(∞, 1 + 4) → 5
D→B: dist[B] = min(4, 5 + (-6)) → -1

dist[A]=0, dist[B]=-1, dist[C]=1, dist[D]=5

2회차:

B→C: dist[C] = min(1, -1 + (-3)) → -4
C→D: dist[D] = min(5, -4 + 4) → 0
D→B: dist[B] = min(-1, 0 + (-6)) → -6

dist[A]=0, dist[B]=-6, dist[C]=-4, dist[D]=0

3회차:

반복적인 relax로 값이 계속 갱신됨 → 음의 사이클 가능성 있음

3단계: 음의 사이클 확인

B→C: dist[C] = -4, dist[B] = -6, w = -3
→ dist[B] + w = -6 + (-3) = -9 < -4 ⇒ 갱신됨
→ 음의 사이클 존재

벨만-포드 알고리즘과 다익스트라 비교

항목	벨만-포드	다익스트라
음의 가중치	가능	불가능 (음의 가중치가 있으면 오작동)
알고리즘 복잡도	O(VE)	O((V+E) logV) (우선순위 큐 사용 시)
사이클 탐지	음의 사이클 탐지 가능	불가능
성능	느림	빠름

알고리즘 튜토리얼