벨만-포드 알고리즘

벨만-포드 알고리즘(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에서 다른 정점까지의 최단 경로를 구하는 예시이다.

그래프:

A --(1)--> B --(-1)--> C
 \                   ^
  \(4)--------------/

단계	d[A]	d[B]	d[C]
초기값	0	∞	∞
1회차	0	1	0
2회차	0	1	0
3회차	0	1	0

모든 간선을 검사한 결과, 더 이상 갱신이 없으므로 음의 사이클은 존재하지 않는다. 최단 경로는 다음과 같다:

• A → B: 거리 1
• A → B → C: 거리 0

구현

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.