벨만-포드 알고리즘
마지막 업데이트
벨만-포드는 출발 노드에서 다른 모든 노드까지의 최단 경로를 찾으며, Dijkstra와 달리 일부 간선 가중치가 음수여도 동작합니다. 무차별 완화 방식으로 작동합니다. 모든 간선을 반복해서 훑고, 그 간선을 지나는 것이 더 짧은 거리를 준다면 대상 노드의 거리를 갱신합니다. 위의 재생을 누르면 잠정 거리가 패스마다 줄어드는 모습을 볼 수 있습니다.
모든 간선에 대한 V - 1번의 패스 후에는 (최대 V - 1개의 간선을 가질 수 있는) 모든 최단 경로가 구해집니다. 이로 인해 O(V · E)가 되어 Dijkstra보다 느리지만, 음수 가중치를 처리하고 음수 가중치 사이클을 검출할 수 있습니다(V번째 패스에서도 간선이 완화되면 최단 경로가 존재하지 않습니다).
시간 및 공간 복잡도
| 척도 | 복잡도 | 비고 |
|---|---|---|
| 시간 | O(V · E) | 모든 E 간선에 대한 V − 1번의 패스 |
| 공간 | O(V) | 노드당 하나의 거리 |
| 음수 가중치 | 지원 | Dijkstra 대비 핵심 장점 |
| 음수 사이클 | 검출 가능 | 완화가 일어나는 V번째 패스가 하나를 알림 |
단계별 진행
| 단계 | 일어나는 일 |
|---|---|
| 1 | 출발지 거리를 0으로, 나머지 전부를 무한대로 설정한다. |
| 2 | 다음 단계를 V − 1번 반복한다. |
| 3 | 각 간선 (u → v, w)에 대해 dist[u] + w < dist[v]인지 확인한다. |
| 4 | 그렇다면 완화한다: dist[v] = dist[u] + w로 설정한다. |
| 5 | 완전한 패스에서 아무 변화가 없으면 조기에 멈춘다. |
풀이 예제
4개 노드 S, A, B, C에서 출발지 S, 간선 S→A (4), S→B (5), A→C (3), B→A (-3)를 이 순서로 완화합니다. 거리는 S=0, 나머지는 모두 ∞에서 시작합니다:
| 패스 | 거리 [S, A, B, C] | 동작 |
|---|---|---|
| Init | [0, ∞, ∞, ∞] | 출발지 거리는 0, 나머지는 모두 무한대. |
| 1 | [0, 2, 5, 7] | S→A를 4, S→B를 5, A→C를 7로 완화하고, 이어서 B→A가 A를 5 + (-3) = 2로 낮춘다. |
| 2 | [0, 2, 5, 5] | 이제 A→C가 C를 2 + 3 = 5로 개선한다. 다른 간선은 완화되지 않는다. |
| 3 | [0, 2, 5, 5] | 어떤 간선도 완화되지 않으므로 거리가 확정된다: A는 S→B→A를 통해 비용 2. |
벨만-포드를 사용해야 할 때
| 사용해야 할 때 | 피해야 할 때 |
|---|---|
| 간선 가중치가 음수일 수 있을 때. | 모든 가중치가 음이 아닐 때(Dijkstra가 더 빠름). |
| 음수 가중치 사이클을 검출해야 할 때. | 그래프가 매우 크고 밀집되어 있을 때 - O(V · E)는 너무 느림. |
| 그래프가 작거나 희소할 때. | 큰 그래프에서 출발지-목적지 단일 질의만 필요할 때. |
| 간단하고 구현하기 쉬운 기준선이 필요할 때. | 가중치가 음이 아니고 지연 시간이 중요할 때. |
Bellman-Ford Algorithm 코드
Python, JavaScript, Java, C++, C로 작성된 깔끔하고 실행 가능한 Bellman-Ford Algorithm 구현입니다. 언어를 선택해 코드를 복사하거나 Coddy 플레이그라운드에서 바로 열어보세요.
Python로 구현한 Bellman-Ford Algorithm 코드
Python
1def bellman_ford(vertices, edges, start):2 dist = {v: float("inf") for v in vertices}3 dist[start] = 04 # Relax every edge V-1 times5 for _ in range(len(vertices) - 1):6 for u, v, w in edges:7 if dist[u] + w < dist[v]:8 dist[v] = dist[u] + w9 # One more pass: any improvement means a negative cycle10 for u, v, w in edges:11 if dist[u] + w < dist[v]:12 raise ValueError("Graph contains a negative-weight cycle")13 return dist14
15
16vertices = ["A", "B", "C", "D", "E"]17edges = [18 ("A", "B", 6), ("A", "C", 7), ("B", "D", 5), ("B", "E", -4),19 ("C", "D", -3), ("D", "B", -2), ("E", "D", 7),20]21
22for node, d in bellman_ford(vertices, edges, "A").items():23 print(f"A -> {node}: {d}")JavaScript로 구현한 Bellman-Ford Algorithm 코드
JavaScript
1const nodes = ["A", "B", "C", "D", "E"];2const edges = [3 ["A", "B", 6], ["A", "C", 7], ["B", "D", 5], ["B", "E", -4],4 ["C", "D", -3], ["D", "B", -2], ["E", "A", 2],5];6
7function bellmanFord(source) {8 const dist = Object.fromEntries(nodes.map((n) => [n, Infinity]));9 dist[source] = 0;10 // Relax every edge V-1 times11 for (let i = 0; i < nodes.length - 1; i++) {12 for (const [u, v, w] of edges) {13 if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;14 }15 }16 // One more pass: any improvement means a negative cycle17 for (const [u, v, w] of edges) {18 if (dist[u] + w < dist[v]) throw new Error("Negative cycle detected");19 }20 return dist;21}22
23console.log("Shortest distances from A:", bellmanFord("A"));Java로 구현한 Bellman-Ford Algorithm 코드
Java
1import java.util.Arrays;2
3public class Main {4 public static void main(String[] args) {5 int n = 5;6 // Directed edges {from, to, weight}; negative weights allowed7 int[][] edges = {8 {0, 1, 6}, {0, 2, 7}, {1, 3, 5}, {1, 2, 8},9 {2, 4, 9}, {3, 1, -2}, {4, 3, 7}, {2, 3, -3}10 };11 int[] dist = new int[n];12 Arrays.fill(dist, Integer.MAX_VALUE);13 dist[0] = 0;14
15 // Relax every edge V-1 times16 for (int i = 0; i < n - 1; i++) {17 for (int[] e : edges) {18 if (dist[e[0]] != Integer.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]]) {19 dist[e[1]] = dist[e[0]] + e[2];20 }21 }22 }23
24 // One more pass: any improvement means a negative cycle25 boolean hasNegativeCycle = false;26 for (int[] e : edges) {27 if (dist[e[0]] != Integer.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]]) {28 hasNegativeCycle = true;29 }30 }31
32 System.out.println("Distances from 0: " + Arrays.toString(dist));33 System.out.println("Negative cycle: " + hasNegativeCycle);34 }35}C++로 구현한 Bellman-Ford Algorithm 코드
C++
1#include <iostream>2#include <vector>3
4struct Edge {5 int from, to, weight;6};7
8int main() {9 const int INF = 1000000000;10 const int n = 5;11 std::vector<Edge> edges = {12 {0, 1, 6}, {0, 2, 7}, {1, 3, 5}, {2, 3, -3},13 {1, 4, -4}, {3, 4, 9}, {2, 1, -2},14 };15 std::vector<int> dist(n, INF);16 dist[0] = 0;17 // Relax every edge V-1 times18 for (int pass = 0; pass < n - 1; ++pass) {19 for (const Edge& e : edges) {20 if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {21 dist[e.to] = dist[e.from] + e.weight;22 }23 }24 }25 // One extra pass: any improvement means a negative cycle26 bool negativeCycle = false;27 for (const Edge& e : edges) {28 if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {29 negativeCycle = true;30 }31 }32 if (negativeCycle) {33 std::cout << "Negative cycle detected\n";34 } else {35 for (int v = 0; v < n; ++v) {36 std::cout << "Distance 0 -> " << v << ": " << dist[v] << "\n";37 }38 }39 return 0;40}C로 구현한 Bellman-Ford Algorithm 코드
C
1#include <stdbool.h>2#include <stdio.h>3
4#define N 55#define INF 10000000006
7typedef struct {8 int from, to, weight;9} Edge;10
11int main(void) {12 Edge edges[] = {13 {0, 1, 6}, {0, 2, 7}, {1, 3, 5}, {2, 3, -3},14 {1, 4, -4}, {3, 4, 9}, {2, 1, -2},15 };16 int m = sizeof(edges) / sizeof(edges[0]);17 int dist[N];18 for (int v = 0; v < N; v++) dist[v] = INF;19 dist[0] = 0;20 // Relax every edge V-1 times21 for (int pass = 0; pass < N - 1; pass++) {22 for (int i = 0; i < m; i++) {23 Edge e = edges[i];24 if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {25 dist[e.to] = dist[e.from] + e.weight;26 }27 }28 }29 // One extra pass: any improvement means a negative cycle30 bool negativeCycle = false;31 for (int i = 0; i < m; i++) {32 Edge e = edges[i];33 if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {34 negativeCycle = true;35 }36 }37 if (negativeCycle) {38 printf("Negative cycle detected\n");39 } else {40 for (int v = 0; v < N; v++) {41 printf("Distance 0 -> %d: %d\n", v, dist[v]);42 }43 }44 return 0;45}벨만-포드 FAQ
벨만-포드의 시간 복잡도는?
벨만-포드는
O(V · E) 시간에 실행됩니다. V - 1번의 패스를 수행하고 각 패스에서 모든 E 간선을 완화합니다. 이는 Dijkstra의 O((V + E) log V)보다 느리며, 음수 간선 가중치를 지원하는 데 따른 대가입니다.Dijkstra 대신 벨만-포드를 언제 사용해야 하나요?
그래프에 음수 간선 가중치가 있을 수 있거나 음수 가중치 사이클을 검출해야 할 때 벨만-포드를 사용하세요. Dijkstra는 더 빠르지만 음이 아닌 가중치에서만 올바릅니다. 흔한 실제 용도는 음수 사이클이 중요한 환율 차익거래 탐지입니다.
벨만-포드는 어떻게 음수 사이클을 검출하나요?
V - 1번의 완화 패스 후, 음수 사이클이 없다면 모든 최단 경로가 확정됩니다. 한 번 더 패스했을 때 여전히 간선을 완화할 수 있다면, 도달 가능한 음수 가중치 사이클이 존재하고 최단 경로는 정의되지 않습니다(비용을 낮추기 위해 무한히 순환할 수 있습니다).벨만-포드와 플로이드-워셜의 차이는 무엇인가요?
벨만-포드는 단일 출발지에서의 최단 경로를
O(V · E)에 계산하는 반면, 플로이드-워셜은 모든 쌍 간 최단 경로를 O(V³)에 계산합니다. 밀집 그래프에서 각 출발지마다 벨만-포드를 실행하면 O(V² · E)가 들기 때문에, 모든 쌍이 필요할 때는 보통 플로이드-워셜이 더 나은 선택입니다. 둘 다 음수 간선을 처리하고 음수 사이클을 표시할 수 있습니다.벨만-포드는 왜 정확히 V - 1번의 패스가 필요한가요?
음수 사이클이 없는 그래프의 어떤 최단 경로도 최대
V - 1개의 간선만 사용합니다. V개를 넘는 노드를 방문하는 경로는 하나를 반복해야 하기 때문입니다. 각 패스는 모든 최단 경로의 간선을 적어도 하나 더 올바르게 완화함을 보장하므로, V - 1번의 패스로 전부 확정할 수 있습니다. 흔한 오해는 패스를 더 하면 결과가 나아진다는 것인데, 음수 사이클이 존재하지 않는 한 결코 나아지지 않습니다.벨만-포드는 조기에 멈출 수 있나요?
네. 모든 간선에 대한 완전한 패스에서 아무것도 완화되지 않으면 모든 거리가 이미 최적이므로
V - 1번의 패스에 도달하기 전에 멈출 수 있습니다. 이 조기 종료 최적화는 빠르게 수렴하는 그래프에서 종종 훨씬 빠르게 만들지만, 최악의 경우 한계는 여전히 O(V · E)입니다.관련 자료
더 많은 시각화
