[알고리즘/그래프] 벨만-포드 알고리즘

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

음수 가중치가 존재할 수 있는 유향 그래프에서 최단 거리를 구하는 알고리즘

 

- 다익스트라와 달리 음수 가중치를 허용

- 음수 사이클(가중치 합이 음수인 사이클) 존재 여부도 판별

 

시간복잡도는 O(VE), 공간복잡도는 O(V).

 

핵심 아이디어

- 에지리스트로 그래프를 구현, 최단 경로 배열 초기화

- 모든 간선을 V−1번(정점 수가 V일 때) 반복적으로 완화(relax)하면, 시작점에서 각 정점까지의 최단 거리가 확정

- 추가로 한 번 더 모든 간선을 점검하여 더 줄어드는 거리가 있다면, 음수 사이클이 존재한다고 결론 내릴 수 있다

언제 쓰나?

간선 가중치에 음수가 포함될 수 있을 때.
최단 거리를 구하면서 음수 사이클 검출도 필요할 때.
그래프가 매우 조밀하지 않거나, V와 E가 너무 크지 않을 때.

 

 

코드

#include <bits/stdc++.h>

struct Edge
{
    int u;
    int v;
    long long w;
};

struct BellmanFordResult
{
    std::vector<long long> dist;
    std::vector<int> parent;
    bool hasNegativeCycle;
};

const long long INF = (1LL << 60);

BellmanFordResult bellman_ford(int n, const std::vector<Edge>& edges, int src)
{
    BellmanFordResult res;
    res.dist.assign(n, INF);
    res.parent.assign(n, -1);
    res.hasNegativeCycle = false;

    res.dist[src] = 0;

    // V-1 번 완화
    for (int i = 0; i < n - 1; ++i)
    {
        bool updated = false;
        for (const auto& e : edges)
        {
            if (res.dist[e.u] == INF)
            {
                continue;
            }
            if (res.dist[e.v] > res.dist[e.u] + e.w)
            {
                res.dist[e.v] = res.dist[e.u] + e.w;
                res.parent[e.v] = e.u;
                updated = true;
            }
        }
        if (!updated)
        {
            break; // 조기 종료
        }
    }

    // 추가 한 번 더 완화되면 음수 사이클 존재
    for (const auto& e : edges)
    {
        if (res.dist[e.u] == INF)
        {
            continue;
        }
        if (res.dist[e.v] > res.dist[e.u] + e.w)
        {
            res.hasNegativeCycle = true;
            break;
        }
    }

    return res;
}