기쁘달

벨만-포드 (Bellman-Ford)

13 min read

개념

음수 가중치가 있는 그래프에서 단일 출발점 최단 경로를 구하는 알고리즘

음수 사이클 탐지 가능

시간복잡도

구현 방식시간복잡도
기본 구현O(VE)
공간복잡도O(V)

특징

장점

  • 음수 가중치 처리: 음수 간선이 있어도 작동
  • 음수 사이클 탐지: 음수 사이클 존재 여부 확인
  • 구현 간단: 모든 간선을 V-1번 반복

단점

  • 느린 속도: O(VE) - 다익스트라보다 느림
  • 밀집 그래프: 간선이 많으면 매우 느림

적용 조건

  • 음수 가중치 있음: 필수 조건
  • 방향/무방향 모두 가능
  • 음수 사이클 없음 (있으면 최단 경로 무한 감소)

구현 방법

기본 구현

def bellman_ford(n, edges, start):
    """벨만-포드 알고리즘"""
    # 거리 초기화
    distances = [float('inf')] * n
    distances[start] = 0
 
    # V-1번 반복
    for _ in range(n - 1):
        # 모든 간선 확인
        for u, v, weight in edges:
            if distances[u] != float('inf') and distances[u] + weight < distances[v]:
                distances[v] = distances[u] + weight
 
    # 음수 사이클 확인 (V번째 반복)
    for u, v, weight in edges:
        if distances[u] != float('inf') and distances[u] + weight < distances[v]:
            return None  # 음수 사이클 존재
 
    return distances
 
# 테스트
# edges: [(출발, 도착, 가중치), ...]
edges = [
    (0, 1, 4),
    (0, 2, 3),
    (1, 2, -2),
    (1, 3, 2),
    (2, 3, 3)
]
 
print(bellman_ford(4, edges, 0))  # [0, 4, 2, 5]
 
# 시간복잡도: O(VE)
# 공간복잡도: O(V)

경로 추적 구현

def bellman_ford_with_path(n, edges, start):
    """경로 추적"""
    distances = [float('inf')] * n
    distances[start] = 0
    previous = [-1] * n
 
    # V-1번 반복
    for _ in range(n - 1):
        for u, v, weight in edges:
            if distances[u] != float('inf') and distances[u] + weight < distances[v]:
                distances[v] = distances[u] + weight
                previous[v] = u
 
    # 음수 사이클 확인
    for u, v, weight in edges:
        if distances[u] != float('inf') and distances[u] + weight < distances[v]:
            return None, None  # 음수 사이클 존재
 
    return distances, previous
 
def get_path(previous, start, end):
    """경로 복원"""
    path = []
    current = end
 
    while current != -1:
        path.append(current)
        current = previous[current]
 
    path.reverse()
    return path if path[0] == start else []
 
# 테스트
edges = [
    (0, 1, 4),
    (0, 2, 3),
    (1, 2, -2),
    (1, 3, 2),
    (2, 3, 3)
]
 
distances, previous = bellman_ford_with_path(4, edges, 0)
print(f"최단 거리: {distances}")
print(f"0→3 경로: {get_path(previous, 0, 3)}")  # [0, 1, 2, 3]

음수 사이클 탐지 전용

def detect_negative_cycle(n, edges):
    """음수 사이클 탐지"""
    distances = [0] * n  # 모든 정점에서 시작 가능하도록 0으로 초기화
 
    # V-1번 반복
    for _ in range(n - 1):
        for u, v, weight in edges:
            if distances[u] + weight < distances[v]:
                distances[v] = distances[u] + weight
 
    # V번째 반복 - 갱신되면 음수 사이클
    for u, v, weight in edges:
        if distances[u] + weight < distances[v]:
            return True  # 음수 사이클 존재
 
    return False
 
# 테스트
# 음수 사이클 있는 경우
edges = [
    (0, 1, 1),
    (1, 2, -3),
    (2, 0, 1)
]
print(detect_negative_cycle(3, edges))  # True
 
# 음수 사이클 없는 경우
edges = [
    (0, 1, 4),
    (1, 2, -2),
    (2, 3, 3)
]
print(detect_negative_cycle(4, edges))  # False

SPFA (Shortest Path Faster Algorithm) 최적화

from collections import deque
 
def spfa(graph, start):
    """SPFA - 벨만-포드 최적화 버전"""
    n = len(graph)
    distances = [float('inf')] * n
    distances[start] = 0
 
    queue = deque([start])
    in_queue = [False] * n
    in_queue[start] = True
    count = [0] * n  # 각 정점이 큐에 들어간 횟수
 
    while queue:
        current = queue.popleft()
        in_queue[current] = False
 
        for neighbor, weight in graph[current]:
            distance = distances[current] + weight
 
            if distance < distances[neighbor]:
                distances[neighbor] = distance
 
                if not in_queue[neighbor]:
                    queue.append(neighbor)
                    in_queue[neighbor] = True
                    count[neighbor] += 1
 
                    # 음수 사이클 탐지 (V번 이상 큐에 들어가면)
                    if count[neighbor] >= n:
                        return None  # 음수 사이클
 
    return distances
 
# 테스트
graph = [
    [(1, 4), (2, 3)],
    [(2, -2), (3, 2)],
    [(3, 3)],
    []
]
 
print(spfa(graph, 0))  # [0, 4, 2, 5]
 
# 평균 O(E), 최악 O(VE)

동작 과정

그래프:
    0 --4--> 1
    |        |
    3      -2
    ↓        ↓
    2 --3--> 3

간선: (0,1,4), (0,2,3), (1,2,-2), (1,3,2), (2,3,3)

초기: distances = [0, ∞, ∞, ∞]

1회차 (모든 간선 확인):
  (0,1,4): distances[1] = 0+4 = 4
  (0,2,3): distances[2] = 0+3 = 3
  (1,2,-2): distances[2] = 4+(-2) = 2
  (1,3,2): distances[3] = 4+2 = 6
  (2,3,3): distances[3] = 2+3 = 5
  distances = [0, 4, 2, 5]

2회차 (모든 간선 확인):
  (0,1,4): 4 ≥ 4, 갱신 안 함
  (0,2,3): 3 ≥ 2, 갱신 안 함
  (1,2,-2): 2 ≥ 2, 갱신 안 함
  (1,3,2): 6 ≥ 5, 갱신 안 함
  (2,3,3): 5 ≥ 5, 갱신 안 함
  distances = [0, 4, 2, 5]

3회차: 갱신 없음

음수 사이클 확인:
  모든 간선 확인 - 갱신 없음 → 음수 사이클 없음

최종: [0, 4, 2, 5]

템플릿

def bellman_ford_template(n, edges, start):
    # 1. 초기화
    distances = [float('inf')] * n
    distances[start] = 0
 
    # 2. V-1번 모든 간선 완화
    for _ in range(n - 1):
        for u, v, weight in edges:
            if distances[u] != float('inf'):
                if distances[u] + weight < distances[v]:
                    distances[v] = distances[u] + weight
 
    # 3. 음수 사이클 확인
    for u, v, weight in edges:
        if distances[u] != float('inf'):
            if distances[u] + weight < distances[v]:
                return None  # 음수 사이클
 
    return distances

핵심 요약

개념설명
원리모든 간선을 V-1번 완화
시간복잡도O(VE)
공간복잡도O(V)
적용 조건음수 가중치 가능
특징음수 사이클 탐지

다른 알고리즘과 비교

알고리즘시간복잡도음수 가중치음수 사이클 탐지
다익스트라O((V+E) log V)불가불가
벨만-포드O(VE)가능가능
플로이드-워셜O(V³)가능가능
SPFA평균 O(E)가능가능

주의사항

1. 음수 사이클

# 음수 사이클이 있으면 최단 경로 무한 감소
edges = [
    (0, 1, 1),
    (1, 2, -3),
    (2, 0, 1)  # 사이클: 0→1→2→0 (합: -1)
]
# 최단 경로가 존재하지 않음

2. 도달 불가 정점

# distances[u] != float('inf') 체크 필수
if distances[u] != float('inf'):
    # 완화 수행

3. V-1번 반복 이유

# 최단 경로는 최대 V-1개의 간선 포함
# (사이클 없이 모든 정점 방문)
# V-1번이면 모든 최단 경로 찾음

자주 나오는 문제 유형

1. 기본 최단 경로 (음수 가중치)

문제: 음수 가중치가 있는 그래프의 최단 경로

def shortest_path_negative(n, edges, start, end):
    """음수 가중치 최단 경로"""
    distances = bellman_ford(n, edges, start)
 
    if distances is None:
        return "음수 사이클 존재"
 
    return distances[end] if distances[end] != float('inf') else "도달 불가"
 
# 테스트
edges = [
    (0, 1, 4),
    (0, 2, 3),
    (1, 2, -2),
    (2, 3, 3)
]
 
print(shortest_path_negative(4, edges, 0, 3))  # 4

2. 음수 사이클에 영향받는 정점

문제: 음수 사이클로 인해 거리가 무한히 감소하는 정점 찾기

def find_affected_by_negative_cycle(n, edges, start):
    """음수 사이클 영향 받는 정점"""
    distances = [float('inf')] * n
    distances[start] = 0
 
    # V-1번 완화
    for _ in range(n - 1):
        for u, v, weight in edges:
            if distances[u] != float('inf') and distances[u] + weight < distances[v]:
                distances[v] = distances[u] + weight
 
    # 음수 사이클 영향 받는 정점 표시
    affected = [False] * n
 
    # V번 더 반복하여 전파
    for _ in range(n):
        for u, v, weight in edges:
            if distances[u] != float('inf') and distances[u] + weight < distances[v]:
                distances[v] = distances[u] + weight
                affected[v] = True
            if affected[u]:
                affected[v] = True
 
    return affected
 
# 테스트
edges = [
    (0, 1, 1),
    (1, 2, -3),
    (2, 1, 1),  # 음수 사이클: 1→2→1
    (2, 3, 1)
]
 
affected = find_affected_by_negative_cycle(4, edges, 0)
print(affected)  # [False, True, True, True]

3. 시간 여행 (타임머신)

문제: 백준 11657번 - 음수 가중치와 사이클 처리

def time_machine(n, edges, start):
    """타임머신 문제"""
    distances = [float('inf')] * n
    distances[start] = 0
 
    # V-1번 완화
    for _ in range(n - 1):
        for u, v, weight in edges:
            if distances[u] != float('inf') and distances[u] + weight < distances[v]:
                distances[v] = distances[u] + weight
 
    # 음수 사이클 확인
    has_negative_cycle = False
    for u, v, weight in edges:
        if distances[u] != float('inf') and distances[u] + weight < distances[v]:
            has_negative_cycle = True
            break
 
    if has_negative_cycle:
        return "음수 사이클"
 
    # 도달 불가한 정점은 -1
    result = []
    for i in range(1, n):
        if distances[i] == float('inf'):
            result.append(-1)
        else:
            result.append(distances[i])
 
    return result
 
# 테스트
edges = [
    (0, 1, 4),
    (0, 2, 3),
    (1, 2, -1),
    (2, 1, 1)
]
 
print(time_machine(3, edges, 0))  # [4, 3]

4. 웜홀 (음수 사이클 탐지)

문제: 백준 1865번 - 웜홀로 과거로 갈 수 있는지

def wormhole(n, edges):
    """웜홀 문제 - 음수 사이클 탐지"""
    # 모든 정점에서 시작 가능
    distances = [0] * n
 
    # V-1번 완화
    for _ in range(n - 1):
        for u, v, weight in edges:
            if distances[u] + weight < distances[v]:
                distances[v] = distances[u] + weight
 
    # 음수 사이클 확인
    for u, v, weight in edges:
        if distances[u] + weight < distances[v]:
            return "YES"  # 과거로 갈 수 있음
 
    return "NO"
 
# 테스트
# 양방향 도로 + 단방향 웜홀
edges = [
    (0, 1, 2), (1, 0, 2),  # 양방향 도로
    (1, 2, 3), (2, 1, 3),
    (0, 2, 1), (2, 0, 1),
    (0, 1, -3)  # 웜홀 (음수)
]
 
print(wormhole(3, edges))  # YES

5. 제한 시간 내 최단 경로

문제: K번 이하로 간선을 사용하여 도달

def bellman_ford_k_edges(n, edges, start, end, k):
    """K개 이하 간선 사용"""
    distances = [[float('inf')] * n for _ in range(k + 1)]
    distances[0][start] = 0
 
    for i in range(k):
        for u, v, weight in edges:
            if distances[i][u] != float('inf'):
                if distances[i][u] + weight < distances[i + 1][v]:
                    distances[i + 1][v] = distances[i][u] + weight
 
        # 이전 단계 복사
        for j in range(n):
            distances[i + 1][j] = min(distances[i + 1][j], distances[i][j])
 
    return distances[k][end]
 
# 테스트
edges = [
    (0, 1, 10),
    (0, 2, 5),
    (1, 3, 1),
    (2, 1, 3),
    (2, 3, 2)
]
 
print(bellman_ford_k_edges(4, edges, 0, 3, 2))  # 7 (0→2→3)

추천 연습 문제

기초

중급

고급

벨만-포드 vs 다익스트라

특성벨만-포드다익스트라
시간복잡도O(VE)O((V+E) log V)
음수 가중치가능불가
음수 사이클탐지 가능탐지 불가
속도느림빠름
사용 시기음수 가중치 있음양수 가중치만

언제 사용할까?

사용 가능

  • 음수 가중치: 필수 상황
  • 음수 사이클 탐지: 사이클 확인 필요
  • 작은 그래프: 정점/간선 수가 적음
  • 시간 제약 없음: 속도보다 정확성

사용 불가

  • 양수 가중치만: 다익스트라가 훨씬 빠름
  • 대용량 그래프: O(VE)가 너무 느림
  • 실시간 처리: 시간 초과 가능

결론: 음수 가중치나 음수 사이클 탐지가 필요할 때 사용!

그래프 뷰

백링크