Algorithm Guidecomplexity: O(V·E)

벨만-포드 (Bellman-Ford)

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

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step

TAP OR HOVER

Bellman-Ford

시작A

패스0 / 3

간선—

상태대기

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 파이썬 구현 코드

벨만-포드 (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

Guide Progress0%