[Algorithm] 벨만-포드 알고리즘
in Algorithm
벨만-포드 알고리즘에 대해 정리해보았습니다.
🎯 1️⃣ 벨만-포드란?
💡 한 문장 정의
“음수 가중치를 허용하며, 음수 사이클 존재 여부까지 판별할 수 있는 최단 경로 알고리즘”
💡 언제 사용하는가?
- 간선 가중치가 음수일 수 있을 때
- “이 그래프에 음수 사이클이 존재하는가?”를 판단해야 할 때
- 최단 경로 자체보다 사이클 판별이 중요한 문제일 때
💡 특징
| 특징 | 설명 |
|---|---|
| 시간복잡도 | O(VE) |
| 공간복잡도 | O(V) |
| 음수 간선 | 처리 가능 |
| 음수 사이클 | 탐지 가능 |
| 그래프 종류 | 방향/무방향 모두 가능 |
| 구현 난이도 | 중간 (반복 구조 이해 필요) |
🧠 2️⃣ 핵심 개념 이해하기
💡 알고리즘의 본질
"모든 간선을 반복적으로 확인하면서,
더 짧은 경로가 발견되면 거리 정보를 갱신하고,
이 갱신이 끝없이 발생하는지를 확인하는 알고리즘"
💡 dist[v]의 의미
dist[v] = 어떤 시작점으로부터
정점 v까지 도달할 수 있는 현재까지의 최소 비용
※ 음수 사이클 탐지 문제에서는 dist의 정확한 값보다 ‘계속 줄어드는지 여부’가 더 중요하다.
🔁 3️⃣ 간선 완화(Relaxation)
💡 간선 완화란?
“간선 u → v를 이용했을 때 더 짧은 경로가 생기면 dist[v]를 갱신하는 과정”
💡 완화 조건
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
}
💡 왜 반복하는가?
- 최단 경로는 최대 V-1개의 간선으로 구성됨
- 한 번의 완화로는 정보가 충분히 퍼지지 않음
- 그래서 모든 간선을 V-1번 반복해서 완화
⚠️ 4️⃣ 음수 사이클 탐지 원리
💡 핵심 아이디어
- 정상적인 그래프라면 → V-1번 완화 이후 더 이상 갱신이 발생하지 않음
- 그런데도 → V번째 완화에서 갱신 발생? → 음수 사이클 존재
💡 의미 해석
"같은 경로를 계속 돌수록
비용이 줄어든다"
= 시간 여행이 가능한 루프
🧩 5️⃣ 코드 구현 (구조 중심)
for (int i = 1; i <= V; i++) {
for (Edge e : edges) {
if (dist[e.to] > dist[e.from] + e.cost) {
dist[e.to] = dist[e.from] + e.cost;
if (i == V) {
// 음수 사이클 발견
}
}
}
}
- 바깥 루프: 반복 횟수 (라운드)
- 안쪽 루프: 모든 간선 완화
- V번째 라운드에서 갱신 발생 여부가 핵심
⏱️ 6️⃣ 시간복잡도와 공간복잡도
- 시간복잡도: O(VE)
- 공간복잡도: O(V)
- 정점 수가 크고 간선이 많으면 느릴 수 있음
⚖️ 7️⃣ 다익스트라와의 비교
| 구분 | 벨만-포드 | 다익스트라 |
|---|---|---|
| 음수 간선 | 가능 | 불가능 |
| 음수 사이클 | 탐지 가능 | 불가 |
| 시간복잡도 | 느림 | 빠름 |
| 사용 목적 | 안정성 / 사이클 판별 | 빠른 최단경로 |
🧪 8️⃣ 실전 문제 적용
- 웜홀 문제
- 시간 여행 / 이익 루프 판별
- “되돌아왔을 때 더 이득인가?” 유형
👉 핵심 질문이 “최단거리”보다 “음수 사이클 존재 여부”라면 벨만-포드를 떠올려야 한다.
