Bellman–Ford 알고리즘

 

Bellman–Ford 알고리즘

: Bellman–Ford 알고리즘은 한 정점에서 모든 정점까지의 최단 거리를 구하는 알고리즘
다익스트라(Dijkstra) 알고리즘과 유사하지만, 음수 가중치 간선이 있는 그래프에서도 사용 가능하다는 차이점이 있음.

• 음수 가중치가 존재할 수 있는 그래프
• 음수 사이클 여부를 판단해야 하는 문제

에서 주로 사용됨

 

• 그래프 유형: 가중치가 있는 방향 그래프
• 음수 간선: 허용됨
• 음수 사이클***: 존재하면 탐지 가능
• 시간 복잡도: O(V × E)

 ***음수 사이클? 

예를 들어, 다음과 같은 간선이 있다면

1 → 2 (4)
2 → 3 (-10)
3 → 1 (3)

이 세 간선을 돌면 4 - 10 + 3 = -3으로 계속 거리가 줄어들게 됨.
즉, 무한히 짧은 경로가 생겨버리기 때문에
벨만-포드는 이런 경우를 감지하고 "음수 사이클 존재"로 판단함

---

알고리즘 원리

벨만-포드 알고리즘은 ‘모든 간선을 V-1번 반복적으로 완화(Relax)’ 하는 방식으로 작동함.

 

• “완화(Relaxation)”

어떤 간선 (u → v, cost = w)에 대해
dist[v] > dist[u] + w 이면,
dist[v] = dist[u] + w 로 갱신한다.

이 과정을 모든 간선에 대해 V-1번 반복
(V는 정점 개수. 이유는, 최단 경로에 포함될 수 있는 간선 수는 최대 V-1개이기 때문)

그 후 한 번 더 반복해서 갱신이 일어난다면,
음수 사이클(Negative Cycle) 이 존재한다는 것을 의미함.

---

 

예시

From	To	Cost
1	2	4
1	3	5
2	3	-2
3	4	3

• 시작 정점: 1
• 음수 간선 존재 (2 → 3, cost = -2)

 

코드로 구현하면

#include <iostream>
#include <vector>
#include <tuple>
using namespace std;

const int INF = 1e9;

int main() {
    int V = 4, E = 4;
    vector<tuple<int, int, int>> edges = {
        {1, 2, 4},
        {1, 3, 5},
        {2, 3, -2},
        {3, 4, 3}
    };

    vector<int> dist(V + 1, INF);
    int start = 1;
    dist[start] = 0;

    // V-1번 반복 (정점 개수 - 1)
    for (int i = 1; i <= V - 1; i++) {
        for (auto [u, v, w] : edges) {
            if (dist[u] != INF && dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
            }
        }
    }

    // 음수 사이클 존재 여부 확인
    bool negative_cycle = false;
    for (auto [u, v, w] : edges) {
        if (dist[u] != INF && dist[v] > dist[u] + w) {
            negative_cycle = true;
            break;
        }
    }

    if (negative_cycle) {
        cout << "음수 사이클이 존재합니다.\n";
    } else {
        cout << "최단 거리 결과:\n";
        for (int i = 1; i <= V; i++) {
            if (dist[i] == INF) cout << "INF ";
            else cout << dist[i] << " ";
        }
        cout << "\n";
    }

    return 0;
}

 

동작과정

반복 횟수	거리 배열(dist)
초기	[0, INF, INF, INF]
1회차	[0, 4, 5, 8]
2회차	[0, 4, 2, 5]
3회차	[0, 4, 2, 5] (변화 없음)

3회차까지 갱신이 없으므로 알고리즘 종료!
만약 4회차(정점 개수번)에도 갱신이 일어났다면 → 음수 사이클 존재

 

출력 결과

최단 거리 결과:
0 4 2 5

 

---

shortest path 탐색 algorithm 비교

 

구분	Floyd–Warshall	Bellman–Ford	Dijkstra
목적	모든 정점 쌍의 최단 경로	한 정점 → 모든 정점 최단 경로	한 정점 → 모든 정점 최단 경로
음수 가중치	허용	허용	❌ 불가능
음수 사이클 탐지	❌ 불가능	✅ 가능	❌ 불가능
시간 복잡도	O(V³)	O(V × E)	O(E log V) (우선순위 큐 사용 시)
공간 복잡도	O(V²)	O(V)	O(V + E)
적합한 경우	모든 경로 관계를 알고 싶을 때	음수 간선이 존재하는 경우	가중치가 양수이고 빠른 계산이 필요한 경우
구현 난이도	쉬움	중간	중간~어려움
대표 활용 예시	그래프 분석, 도시 간 거리표 계산	음수 사이클 감지, 금융 그래프	네비게이션, 네트워크 라우팅