Oh My Algorithm
Algorithm Guidecomplexity: O(V·E)

벨만-포드 (Bellman-Ford)

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

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step
Bellman-Ford
45-336Ad=0Bd=∞Cd=∞Dd=∞

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

Logic Node1 / 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

04 자주 묻는 질문

FAQ
벨만-포드 (Bellman-Ford)란 무엇인가요?+

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

벨만-포드 (Bellman-Ford)의 시간복잡도는 어떻게 되나요?+

벨만-포드 (Bellman-Ford)의 시간복잡도는 O(V·E) 입니다. 시각화의 단계별 진행을 따라가며 왜 이런 복잡도가 나오는지 직접 확인할 수 있습니다.

벨만-포드 (Bellman-Ford)은(는) 어디에 사용하나요?+

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

벨만-포드 (Bellman-Ford)를 쉽게 비유하면?+

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

→ 그래프 전체 보기Related
🕸위상 정렬 (Topological Sort)
O(V+E)
🕸다익스트라 (Dijkstra)
O(E log V)
🕸크루스칼 (Kruskal MST)
O(E log E)
🕸프림 (Prim MST)
O(E log V)
Guide Progress0%