Algorithm Guidecomplexity: O(V·E)

벨만-포드 (Bellman-Ford)

음수 간선이 있어도 동작하는 최단 경로 알고리즘입니다. 모든 간선을 V−1번 반복 완화하면 최단 거리가 수렴하며, 한 번 더 완화되면 음수 사이클이 존재함을 검출합니다. 다익스트라보다 느리지만 더 일반적입니다.

01벨만-포드 (Bellman-Ford)

알고리즘 작동 원리 탐색

벨만-포드를 시작합니다. 시작 노드는 0, 나머지는 ∞. 모든 간선을 훑는 일을 세 번 반복하며, 음수 가중치도 다룹니다.

패스 1 · B에서 D로 가는 간선부터 봅니다. B까지 가는 길을 아직 몰라 더할 것이 없어 건너뜁니다.

A에서 B로 가면 4. 처음 재 보는 거리라 그대로 적습니다.

A에서 C로 가면 5. 이쪽도 처음이라 그대로 적습니다.

C에서 B로 가는 간선은 −3입니다. C를 거쳐 오면 2가 되어, 방금 적은 4보다 짧아집니다.

C에서 D로 가면 11. 여기까지가 첫 번째 훑기입니다.

패스 2 · B가 2로 줄어든 덕에 D까지도 5로 짧아집니다. 한 번의 훑기로는 닿지 못했던 개선입니다.

남은 간선은 더 줄일 곳이 없습니다. 갱신 없이 두 번째 훑기를 마칩니다.

패스 3 · 모든 간선을 다시 봐도 바뀌는 값이 없어 수렴했습니다. 이어서 음수 사이클이 있는지 확인합니다.

완료 · A에서 D까지 최단 경로 A → C → B → D (거리 5). 음수 사이클이 없어 결과가 유효합니다.

Live Python

1def bellman_ford(edges, V, start):

2 dist = [INF] * V

# dist[A] = 0

3 dist[start] = 0

4 for i in range(V - 1):

5 for u, v, w in edges:

6 if dist[u] + w < dist[v]:

7 dist[v] = dist[u] + w

8 for u, v, w in edges: # negative cycle check

9 if dist[u] + w < dist[v]:

10 raise ValueError('negative cycle')

11 return dist

1 / 10

02 쉽게 이해하기

For Everyone

🔑핵심 동작

모든 간선을 정점 수만큼 반복해 훑으며 더 짧은 경로가 있으면 갱신합니다. 느린 대신 음수 가중치를 다루고 음수 사이클도 찾아냅니다.

💡쉽게 말하면

모든 간선을 V−1번 반복 완화해 최단 거리를 구합니다.

느리지만 음수 간선도 처리하고 음수 사이클도 검출해요.

📍어디에 쓰나

–음수 간선 그래프
–환율 차익 거래 탐지

03 파이썬 구현 코드

벨만-포드 (Bellman-Ford)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.

core_implementation.py

def bellman_ford(edges, V, start):
    dist = [float("inf")] * V
    dist[start] = 0
    for _ in range(V - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            raise ValueError("negative cycle")
    return dist