Algorithm Guidecomplexity: O(V·E)

벨만-포드 (Bellman-Ford)

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

01 Explore How It Works

Interactive Step-by-Step

HOVER OR SCROLL

Bellman-Ford

Bellman-Ford 시작. dist[A]=0, 나머지는 ∞. 간선 전체를 V−1=3번 반복 완화하며, 음수 간선도 다룹니다.

Logic Node1 / 10

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

02 Understand It Simply

For Everyone

🔑Analogy

모든 길을 여러 번 훑어 더 빠른 우회로가 있으면 계속 갱신하는 것.

💡In Plain Words

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

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

📍Where It's Used

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

03 Python Implementation

A clean, readable reference implementation of the core logic of 벨만-포드 (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