24. 벨만포드

벨만포드

빠른 설명

벨만포드는 한 시작점에서 모든 정점까지의 최단거리를 구하는 알고리즘이다. 다익스트라와 달리 음수 간선이 있어도 사용할 수 있으며, 음수 사이클도 감지할 수 있다.

언제 쓰는가

• 음수 간선이 있는 최단거리 문제
• 음수 사이클 존재 여부를 확인해야 할 때
• 정점/간선 수가 너무 크지 않을 때

시간복잡도

• $O(VE)$

참고자료

• CP-Algorithms - Bellman-Ford
• Wikipedia - Bellman-Ford algorithm
• GeeksforGeeks - Bellman-Ford Algorithm
• 나무위키 - 벨먼-포드 알고리즘

C++ 코드

#include <algorithm>
#include <deque>
#include <functional>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
 
struct Edge {
    int from, to, cost;
};
 
const long long INF = (1LL << 60);
 
int main() {
    int n = 4;
    vector<Edge> edges = {
        {0, 1, 4},
        {0, 2, 5},
        {1, 2, -2},
        {2, 3, 3},
    };
 
    vector<long long> dist(n, INF);
    dist[0] = 0;
 
    for (int i = 0; i < n - 1; i++) {
        for (auto e : edges) {
            if (dist[e.from] == INF) continue;
            dist[e.to] = min(dist[e.to], dist[e.from] + e.cost);
        }
    }
 
    bool has_negative_cycle = false;
    for (auto e : edges) {
        if (dist[e.from] != INF && dist[e.to] > dist[e.from] + e.cost) {
            has_negative_cycle = true;
        }
    }
 
    cout << has_negative_cycle << '\n';
}

Python 코드

INF = 10**18
n = 4
edges = [
    (0, 1, 4),
    (0, 2, 5),
    (1, 2, -2),
    (2, 3, 3),
]
 
dist = [INF] * n
dist[0] = 0
 
for _ in range(n - 1):
    for frm, to, cost in edges:
        if dist[frm] == INF:
            continue
        dist[to] = min(dist[to], dist[frm] + cost)
 
has_negative_cycle = False
for frm, to, cost in edges:
    if dist[frm] != INF and dist[to] > dist[frm] + cost:
        has_negative_cycle = True
 
print(has_negative_cycle)