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

July 06, 2024

벨만-포드(Bellman-Ford) 알고리즘은 한 노드에서 다른 모든 노드까지의 최단 거리를 구하는 알고리즘입니다. 다익스트라와 달리 간선의 가중치가 음수인 경우에도 최단 거리를 구할 수 있으며, 음수 순환(Negative Cycle)의 존재 여부도 감지할 수 있습니다.

벨만-포드 vs 다익스트라

두 알고리즘 모두 단일 출발점 최단 경로를 구하지만, 동작 방식과 적용 가능한 상황이 다릅니다.

아래 그래프를 예시로 비교해봅니다.

노드: 1, 2, 3
간선: 1→3 (비용 10), 1→2 (비용 20), 2→3 (비용 -15)

1번 노드에서 3번 노드까지의 최단 경로는 육안으로 보면 1→2→3 (비용: 20 + (-15) = 5)입니다.

그러나 다익스트라는 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택하므로, 먼저 비용이 10인 1→3 경로를 선택해버립니다. 음수 간선이 있으면 이처럼 잘못된 결과가 나올 수 있습니다.

반면 벨만-포드는 매 반복마다 모든 간선을 전부 확인하므로 1→2→3 경로를 올바르게 탐색해 최단 거리 5를 구할 수 있습니다.

구분	다익스트라	벨만-포드
탐색 방식	최단 거리 노드 우선 선택	매 반복마다 모든 간선 확인
음수 가중치	❌ 사용 불가	✅ 사용 가능
음수 순환 감지	❌ 불가	✅ 가능
시간 복잡도	O(E log V)	O(VE)

모든 간선의 가중치가 양수라면 다익스트라, 음수 간선이 포함되어 있다면 벨만-포드를 사용합니다.

음수 순환(Negative Cycle)이란?

음수 순환은 순환 경로의 총 비용이 음수인 경우를 말합니다.

예시: 2→3 (비용 2), 3→5 (비용 1), 5→2 (비용 -4)
     2→3→5→2의 총 비용 = 2 + 1 + (-4) = -1

이 경우 순환을 계속 반복할수록 비용이 무한히 줄어들기 때문에 최단 거리를 정의할 수 없습니다. 따라서 벨만-포드 알고리즘은 최단 거리 탐색 이후 음수 순환 존재 여부를 반드시 확인해야 합니다.

동작 단계

출발 노드를 설정하고 거리를 0으로, 나머지 노드의 거리는 무한대(INF)로 초기화합니다.
아래 과정을 (V - 1)번 반복합니다. (V = 정점의 수)
1. 모든 간선 E개를 하나씩 확인합니다.
2. 각 간선을 거쳐 다른 노드로 가는 비용을 계산해 최단 거리 테이블을 갱신합니다.
V번째 반복에서도 거리 테이블이 갱신된다면 음수 순환이 존재하는 것입니다.

V - 1번 반복하는 이유: 최단 경로는 최대 V - 1개의 간선으로 이루어지기 때문입니다. V - 1번 반복 후에는 모든 노드의 최단 거리가 확정됩니다.

동작 예시

아래 그래프에서 1번 노드를 출발점으로 최단 거리를 구합니다.

노드: 1, 2, 3, 4, 5
간선: 1→2 (1), 1→3 (4), 2→3 (2), 2→4 (5), 3→4 (1), 4→5 (-3)

라운드	2	3	4	5
초기	∞	∞	∞	∞
1라운드	1	3	4	∞
2라운드	1	3	4	1
3라운드	1	3	4	1
4라운드	1	3	4	1

4라운드(V - 1번째)에서 더 이상 갱신이 없으므로 음수 순환은 없으며, 최단 거리가 확정됩니다.

Python 구현

import sys

INF = int(1e9)

def bellman_ford(start, v, edges):
    # 최단 거리 테이블 초기화
    distance = [INF] * (v + 1)
    distance[start] = 0

    # V - 1번 반복 (+ 1번은 음수 순환 감지용)
    for i in range(v):
        for cur_node, next_node, edge_cost in edges:
            # 현재 노드에 도달할 수 있고, 더 짧은 경로가 존재하면 갱신
            if distance[cur_node] != INF and distance[next_node] > distance[cur_node] + edge_cost:
                distance[next_node] = distance[cur_node] + edge_cost
                # V번째 라운드에서도 갱신된다면 음수 순환 존재
                if i == v - 1:
                    return None  # 음수 순환 존재

    return distance


# 사용 예시 (BOJ 11657)
def main():
    input_data = sys.stdin.readline
    v, e = map(int, input_data().split())

    edges = []
    for _ in range(e):
        a, b, c = map(int, input_data().split())
        edges.append((a, b, c))

    result = bellman_ford(1, v, edges)

    if result is None:
        # 음수 순환 존재
        print(-1)
    else:
        for i in range(2, v + 1):
            if result[i] == INF:
                print(-1)  # 도달 불가
            else:
                print(result[i])


main()

코드 흐름 설명

for i in range(v):               # V번 반복 (V-1번 탐색 + 1번 음수 순환 감지)
    for cur, nxt, cost in edges: # 모든 간선 확인
        if distance[cur] != INF and distance[nxt] > distance[cur] + cost:
            distance[nxt] = distance[cur] + cost
            if i == v - 1:       # V번째 라운드에서 갱신 = 음수 순환
                return None

핵심 조건인 distance[cur] != INF는 아직 출발점에서 도달하지 못한 노드를 통해 잘못된 갱신이 일어나는 것을 방지합니다.

시간 복잡도

연산	시간 복잡도
전체	O(VE)
V번 반복 × E개 간선 확인	O(V) × O(E) = O(VE)

다익스트라(O(E log V))보다 느리지만, 음수 가중치와 음수 순환까지 처리할 수 있다는 점에서 활용 범위가 넓습니다.

최단 경로 알고리즘 종합 비교

알고리즘	음수 가중치	음수 순환 감지	시간 복잡도	특징
다익스트라	❌	❌	O(E log V)	단일 출발점, 빠름
벨만-포드	✅	✅	O(VE)	단일 출발점, 음수 처리
플로이드-워샬	✅	✅	O(V³)	모든 쌍 최단 경로