벨만-포드(Bellman-Ford)

벨만-포드(Bellman-Ford) 알고리즘이란?

한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘입니다. 음수 간선이 있는 경우에도 최단 거리를 구할 수 있습니다. 모든 간선에 대해 이완 작업을 V-1 번 반복하고, 각 반복마다 모든 간선 E 를 확인 하므로 𝑂(𝑉×𝐸) 의 시간복잡도를 가집니다.

---

동작 방식

1. 최단 거리테이블을 모두 무한대로 초기화
2. 전체 간선에 대해 V-1 번 아래의 작업을 반복
   • 각 간선 (u → v)에 대해 v.distance > u.distance + weight이면 갱신
3. 음수 사이클 탐지
   • 마지막으로 모든 간선을 한번 더 확인
   • 만약 이 단계에서 거리 테이블이 또 갱신된다면 음수 사이클 존재

예시

아래와 같은 방향 그래프(Directed Graph)가 있다고 가정해 보겠습니다. A를 시작 정점으로 설정합니다. 이 그래프에는 음수 가중치 간선(E -> D)이 포함되어 있습니다.

graph TD
    A -- "-1" --> B;
    A -- "4" --> C;
    B -- "3" --> C;
    B -- "2" --> D;
    B -- "2" --> E;
    D -- "1" --> B;
    C -- "5" --> D;
    E -- "-3" --> D;

• 정점(V): 5개 (A, B, C, D, E)
• 간선(E): 8개
• 시작 정점: A
• 알고리즘은 (V-1) = 4번의 반복을 수행합니다.

초기화

알고리즘을 시작하기 전, 시작점 A의 거리는 0으로, 나머지는 모두 무한대 로 초기화합니다.

정점	A	B	C	D	E
거리	0	∞	∞	∞	∞

k=1

모든 간선에 대해 완화(Relaxation)를 1회 진행합니다.

간선 (u→v, w)	dist[u] + w < dist[v] ?	결과	테이블 갱신
A → B (-1)	0 + (-1) < ∞	True	B = -1
A → C (4)	0 + 4 < ∞	True	C = 4
B → C (3)	-1 + 3 < 4	True	C = 2
B → D (2)	-1 + 2 < ∞	True	D = 1
B → E (2)	-1 + 2 < ∞	True	E = 1
D → B (1)	1 + 1 < -1	False	-
C → D (5)	2 + 5 < 1	False	-
E → D (-3)	1 + (-3) < 1	True	D = -2

E -> D 간선에 의해 D의 거리가 1에서 -2로 추가 갱신되었습니다.

정점	A	B	C	D	E
거리	0	-1	2	-2	1

k=2

갱신된 값을 기준으로 모든 간선을 다시 확인합니다.

간선 (u→v, w)	dist[u] + w < dist[v] ?	결과	테이블 갱신
A → B (-1)	0 + (-1) < -1	False	-
A → C (4)	0 + 4 < 2	False	-
B → C (3)	-1 + 3 < 2	False	-
B → D (2)	-1 + 2 < -2	False	-
B → E (2)	-1 + 2 < 1	False	-
D → B (1)	-2 + 1 < -1	False	-
C → D (5)	2 + 5 < -2	False	-
E → D (-3)	1 + (-3) < -2	False	-

이번 반복에서는 어떤 값도 갱신되지 않았습니다.

정점	A	B	C	D	E
거리	0	-1	2	-2	1

k=3, k=4

2번째 반복에서 더 이상 거리 갱신이 없었으므로, 3번째와 4번째 반복에서도 테이블의 변화는 없습니다. 벨만-포드 알고리즘은 최악의 경우를 대비해 항상 (V-1)번의 반복을 보장합니다.

---

최종 결과 및 음수 사이클 확인

1. (V-1)번 반복 후, 최종 최단 거리 테이블은 다음과 같습니다.

정점	A	B	C	D	E
거리	0	-1	2	-2	1

2. 음수 사이클 확인: 마지막으로 모든 간선을 한 번 더 확인합니다. 이때 만약 거리가 또 갱신된다면 음수 사이클이 존재하는 것이지만, 이 예시에서는 갱신이 일어나지 않으므로 음수 사이클은 없습니다.

따라서 시작점 A에서 각 정점까지의 최단 거리는 위 표와 같이 확정됩니다.

---

코드

#include <algorithm>
#include <iostream>
#include <tuple>
#include <vector>
 
using namespace std;
 
// 간선 정보를 위한 타입 별칭
using Edge = tuple<int, int, int>;
const int INF = INT_MAX;
int V;
 
/**
 * 벨만-포드 알고리즘을 수행하고 결과를 직접 출력하는 함수
 */
void bellmanFord(const vector<Edge> &edges, int start_node) {
	int dist[7];
 
	// --- 배열 초기화 ---
	fill(dist, dist + 5, INF);
	dist[start_node] = 0;
 
	int u, v, w;
	// --- 간선 완화 반복 (V-1 번) ---
	for (int i = 0; i < V - 1; ++i) {
		for (const auto &edge : edges) {
			tie(u, v, w) = edge;
 
			if (dist[u] != INF && dist[u] + w < dist[v]) {
				dist[v] = dist[u] + w;
			}
		}
	}
 
	// --- 음수 사이클 확인 ---
	for (const auto &edge : edges) {
		tie(u, v, w) = edge;
 
		if (dist[u] != INF && dist[u] + w < dist[v]) {
			return; // 음수 사이클 발견 시 함수 종료
		}
	}
 
	// --- 결과 출력 ---
	cout << "시작 정점 " << (char)('A' + start_node)
		 << " 로부터의 최단 거리:\n";
	for (int i = 0; i < V; ++i) {
		cout << "정점 " << (char)('A' + i) << " 까지: ";
		if (dist[i] == INF) {
			cout << "도달할 수 없음\n";
		} else {
			cout << dist[i] << "\n";
		}
	}
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
 
	// 그래프 정의
	V = 5;
	vector<Edge> edges = {{0, 1, -1}, {0, 2, 4}, {1, 2, 3}, {1, 3, 2},
						  {1, 4, 2},  {3, 1, 1}, {2, 3, 5}, {4, 3, -3}};
	int start_node = 0;
 
	// 벨만-포드 함수 호출
	bellmanFord(edges, start_node);
 
	return 0;
}
 

---

참고

• 코딩 테스트를 위한 벨만 포드 알고리즘 7분 핵심 요약