벨만-포드 알고리즘

벨만-포드 알고리즘(Bellman-Ford algorithm, 벨만-포드 算法)은 그래프에서 하나의 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 구하는 알고리즘으로, 음의 가중치를 가진 간선이 존재하는 경우에도 사용할 수 있다.

개요

벨만-포드 알고리즘은 리처드 벨만(Richard Bellman)과 레스터 포드(Lester Ford)에 의해 제안된 알고리즘으로, 다익스트라 알고리즘과는 달리 음의 가중치를 허용한다. 이 알고리즘은 동적 계획법에 기반하여 최단 경로를 반복적으로 개선하며, 음의 사이클(negative cycle)의 존재 여부도 탐지할 수 있는 특징이 있다.

동작 원리

그래프 G = (V, E)와 시작 정점 s가 주어졌을 때, 다음과 같은 방식으로 알고리즘이 진행된다.

• 모든 정점 v ∈ V에 대해 거리 d[v]를 ∞로 초기화하고, d[s] = 0으로 설정한다.
• 간선 (u, v) ∈ E에 대해 d[v] > d[u] + w(u, v)인 경우, d[v] ← d[u] + w(u, v)로 업데이트한다.
• 위의 간선 완화를 총 V-1회 반복한다.
• 이후 모든 간선을 한 번 더 검사하여, 여전히 d[v] > d[u] + w(u, v)인 간선이 존재하면 음의 사이클이 존재하는 것이다.

알고리즘 복잡도

벨만-포드 알고리즘의 시간 복잡도는 O(VE)이다. 이는 모든 간선을 최대 V-1회 순회하기 때문이다. 따라서 정점 수가 많고 간선이 많은 밀집 그래프에서는 성능이 저하될 수 있다.

예시

다음은 음의 가중치 간선을 포함하는 예제 그래프와 벨만-포드 알고리즘 수행 과정을 나타낸 것이다.

그래프 구조:

간선 목록: 아래 순서대로 순회한다. 벨만-포드는 순서에 따라 알고리즘의 중간 전개가 달라질 수 있다.

• A → B (6)

• A → C (7)
• B → C (8)
• B → D (5)
• B → E (-4)
• C → D (-3)
• C → E (9)
• D → B (-2)
• E → D (7)

시작 정점: A

거리 테이블 (d[i]는 정점 i까지의 최단 거리):

반복 단계	A	B	C	D	E
초기값	0	∞	∞	∞	∞
1회 반복	0	2	7	4	2
2회 반복	0	2	7	4	−2
3회 반복	0	2	7	4	−2
4회 반복	0	2	7	4	−2

1회 반복 – 간선별 처리

1. A → B (6): A = 0이므로 B = 0 + 6 = 6 → B 갱신
2. A → C (7): A = 0이므로 C = 0 + 7 = 7 → C 갱신
3. B → C (8): B = 6이므로 C = 6 + 8 = 14 → 기존 C = 7이므로 변화 없음
4. B → D (5): B = 6이므로 D = 6 + 5 = 11 → D 갱신
5. B → E (−4): B = 6이므로 E = 6 − 4 = 2 → E 갱신
6. C → D (−3): C = 7이므로 D = 7 − 3 = 4 → D 갱신 (기존 11 → 4)
7. C → E (9): C = 7이므로 E = 7 + 9 = 16 → 기존 E = 2이므로 변화 없음
8. D → B (−2): D = 4이므로 B = 4 − 2 = 2 → B 갱신 (기존 6 → 2)
9. E → D (7): E = 2이므로 D = 2 + 7 = 9 → 기존 D = 4이므로 변화 없음

2회 반복 – 간선별 처리

1. A → B (6): A = 0이므로 B = 0 + 6 = 6 → 기존 B = 2이므로 변화 없음
2. A → C (7): A = 0이므로 C = 0 + 7 = 7 → 기존 C = 7이므로 변화 없음
3. B → C (8): B = 2이므로 C = 2 + 8 = 10 → 기존 C = 7이므로 변화 없음
4. B → D (5): B = 2이므로 D = 2 + 5 = 7 → 기존 D = 4이므로 변화 없음
5. B → E (−4): B = 2이므로 E = 2 − 4 = −2 → E 갱신 (기존 2 → −2)
6. C → D (−3): C = 7이므로 D = 7 − 3 = 4 → 기존 D = 4이므로 변화 없음
7. C → E (9): C = 7이므로 E = 7 + 9 = 16 → 기존 E = −2이므로 변화 없음
8. D → B (−2): D = 4이므로 B = 4 − 2 = 2 → 기존 B = 2이므로 변화 없음
9. E → D (7): E = −2이므로 D = −2 + 7 = 5 → 기존 D = 4이므로 변화 없음

3회 반복 & 4회 반복

• 모든 간선 검사 시 더 이상 갱신 없음 (거리 안정화됨)
• 정점이 5개이므로 5 - 1 = 4회 까지만 반복된다.

구현

def bellman_ford(graph, start):
    distance = {v: float('inf') for v in graph}
    distance[start] = 0

    for _ in range(len(graph) - 1):
        for u in graph:
            for v, w in graph[u]:
                if distance[u] + w < distance[v]:
                    distance[v] = distance[u] + w

    for u in graph:
        for v, w in graph[u]:
            if distance[u] + w < distance[v]:
                raise ValueError("음의 사이클이 존재합니다.")

    return distance

장단점

장점

• 음의 가중치 허용
• 음의 사이클 탐지 가능
• 간단한 구현

단점

• 시간 복잡도가 O(VE)로 느림

• 밀집 그래프에서는 비효율적
• 음의 사이클 존재 시 경로 무의미

같이 보기

• 다익스트라 알고리즘
• 플로이드-워셜 알고리즘
• 최단 경로 알고리즘
• 그래프 이론
• 동적 계획법

참고 문헌

• Bellman, R. (1958). On a routing problem. Quarterly of Applied Mathematics, 16(1), 87–90.
• Ford, L. R. (1956). Network flow theory. RAND Corporation Report P-923.