벨만-포드 알고리즘

벨만-포드 알고리즘(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 → D (5)
• B → C (8)
• 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회 반복

• A → B: 0 + 6 = 6 → B = 6, 이후 D→B에서 4 + (−2) = 2로 한 번 더 갱신 → B = 2
• A → C: 0 + 7 = 7 → C = 7
• B → D: 2 + 5 = 7 → (변경 없음, D = 4)
• B → C: 2 + 8 = 10 → (변경 없음, C = 7)
• B → E: 2 + (−4) = −2 → E = 2
• C → D: 7 + (−3) = 4 → D = 4
• C → E: 7 + 9 = 16 → (변경 없음, E = 2)
• D → B: 4 + (−2) = 2 → B = 2
• E → D: 2 + 7 = 9 → (변경 없음, D = 4)

2회 반복

• B → E: 2 + (−4) = −2 → E = −2
• E → D: −2 + 7 = 5 → (변경 없음, D = 4)
• 나머지 간선 검사 시 갱신 없음

3회 반복 & 4회 반복

• 모든 간선 검사 시 더 이상 갱신 없음 (거리 안정화)

최종 결과:

• A: 0
• B: 2
• C: 7
• D: 4
• E: −2

구현

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.