벨만-포드 알고리즘

벨만-포드 알고리즘(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회 순회하기 때문이다. 따라서 정점 수가 많고 간선이 많은 밀집 그래프에서는 성능이 저하될 수 있다.

예시

다음은 벨만-포드 알고리즘을 통해 시작 정점 1에서 다른 모든 정점까지의 최소 비용 경로를 구하는 예시이다. 그래프는 다음과 같다.

그래프:

1 --(1)--> x --(1)--> y --(1)--> z --(1)--> t  
1 --(3)--> y  
x --(7)--> t

이 그래프에서 정점 1을 시작점으로 하여 각 정점까지의 최소 비용을 반복적으로 계산하는 과정을 표로 나타내면 다음과 같다. 이때, cₖ[i]는 k개의 간선을 사용해 정점 i에 도달하는 최소 비용을 의미한다.

i	1	x	y	z	t
c₀[i]	0	∞	∞	∞	∞
c₁[i]	0	1	3	∞	7
c₂[i]	0	1	2	4	7
c₃[i]	0	1	2	3	5
c₄[i]	0	1	2	3	4

계산 과정

• c₀[i]: 시작점 1에서만 거리 0, 나머지는 무한대로 초기화
• c₁[i]: 정점 1에서 직접 도달 가능한 정점 x, y, t의 비용을 반영
  • x: 1 → x (1)
  • y: 1 → y (3)
  • t: 1 → x → t (1 + 7 = 8), 하지만 직접 경로 1 → x 존재, t는 아직 최소값 7

• c₂[i]: 이전 값 기반으로 간선 relax 수행
  • y: x → y 통해 1 + 1 = 2 → 갱신
  • z: y → z 통해 2 + 2 = 4 → 갱신

• c₃[i]: z → t 경로 반영 → t = 3 + 1 = 4
• c₄[i]: 더 이상 개선 없음 → 최종 결과 도출

최종적으로 정점 1에서 각 정점까지의 최소 비용은 다음과 같다.

• x: 1
• y: 2
• z: 3
• t: 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.