[Computer Algorithms] Bellman-Ford Algorithm (벨만-포드 알고리즘)

벨만-포드 알고리즘 (Bellman-Ford Algorithm)

벨만-포드 알고리즘은 가중 그래프에서 최단 경로를 찾는 알고리즘이다. 다익스트라 알고리즘과 비슷하지만, 음수 가중치(edge weight)를 가진 그래프도 처리할 수 있다는 점이 큰 차이점이다.

 

• 알고리즘 개요
  • 그래프 유형: 가중치 그래프(음수 가중치 가능), 방향 그래프(Directed Graph)
  • 시간 복잡도: O(VE) (V: 정점 개수, E: 간선 개수)
  • 장점: 음수 가중치를 가진 그래프에서도 최단 경로 계산 가능
  • 단점: 다익스트라(O((V+E) log V))에 비해 느림
  • 추가 기능: 음수 사이클(Negative Cycle) 존재 여부도 확인 가능
• 알고리즘 동작 과정

1. 모든 정점의 거리를 무한대(∞)로 초기화하고, 시작 정점은 0으로 설정.
2. V - 1번 반복하면서 모든 간선을 확인하고, 더 짧은 거리가 발견되면 업데이트한다. V - 1번 반복하는 이유는, 어떤 시작 정점에서 다른 정점으로 가는 최단 경로의 최대 간선 개수는 V - 1개이기 때문이다.
3. 추가로 한 번 더 반복하여 거리 값이 갱신되는 간선이 있다면 음수 사이클 존재 판별 가능.

 

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
#include <algorithm>
#define endl '\n'
using namespace std;

const int INF = 987654321;
int N, M, S;
bool flag;
vector<int> dist;
vector<pair<int, int>> graph[501];

void input()
{
    cin >> N >> M >> S;
    for (int i = 0; i <= N; i++)
    {
        graph[i].clear();
    }
    for (int i = 0; i < M; i++)
    {
        int S, E, T;
        cin >> S >> E >> T;
        graph[S].push_back({E, T});
    }
}

bool bellmanFord(int s)
{
    dist.resize(N + 1, INF);
    dist[s] = 0;
    vector<int> updatedNodes; // 갱신된 노드 저장

    // (N-1)번 반복: 최단 거리 갱신
    for (int i = 1; i < N; i++)
    {
        updatedNodes.clear();
        for (int j = 1; j <= N; j++)
        {
            int curNode = j;
            for (auto next : graph[curNode])
            {
                int nextNode = next.first;
                int weight = next.second;
                if (dist[nextNode] > dist[curNode] + weight)
                {
                    dist[nextNode] = dist[curNode] + weight;
                    updatedNodes.push_back(nextNode); // 갱신된 노드 저장
                }
            }
        }
        if (updatedNodes.empty())
            break; // 갱신된 노드가 없으면 조기 종료
    }

    // (N번째 루프) 음수 사이클 확인
    for (int curNode : updatedNodes) // 갱신된 노드들만 검사
    {
        for (auto next : graph[curNode])
        {
            int nextNode = next.first;
            int weight = next.second;
            if (dist[nextNode] > dist[curNode] + weight)
            {
                return false; // 음수 사이클 존재
            }
        }
    }

    return true; // 음수 사이클 없음
}

void solution()
{
    if (!bellmanFord(S))
    {
        flag = true;
        return;
    }
}

void output()
{
    if (!flag)
    {
        for (int i = 1; i <= N; i++)
        {
            cout << S << "->" << i << ": " << dist[i] << endl;
        }
    }
    else
    {
        cout << "Negative Cycle Detected." << endl;
    }
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    input();
    solution();
    output();

    return 0;
}

입력 예제 1
3 4 1
1 2 2
1 3 4
2 3 1
3 1 -3

출력 예제 1
1->1: 0
1->2: 2
1->3: 3

입력 예제 2
3 3 1
1 2 3
2 3 4
3 1 -8

출력 예제 2
Negative Cycle Detected.