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

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

시간 복잡도 : O(VE)

최단거리를 구하는 알고리즘으로, 다익스트라 알고리즘과 다르게 음수의 간선이 존재하는 경우에도 수행 가능하다.

ex) 벨만-포드 알고리즘 예제(백준 11657)

최단거리에 대한 갱신을 N-1번 반복해야 한다.

음수가 없다고 생각했을 때, 최소한 N-1번 반복해야 시작점으로부터 각 노드별 최단 거리를 알 수 있기 때문이다(아래 사진 참고).

따라서, N-1번을 수행 후, 음수 사이클이 존재하는지 한 번 더 검사하면 된다.

존재한다면 N-1번 이후에도 추가 검사를 진행할 때마다 최소 거리 값에 대한 배열(벡터)이 반복적으로 갱신될 것이다.

#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <stdio.h>

using namespace std;
int n, m;
int INF = 2147000000;

// 간선 정보를 저장하는 벡터
vector<pair<pair<int, int>, int>> a;

// 최단 거리를 저장하는 벡터
vector<long long> d(501);

// 음수 사이클 여부 체크
bool mCycle = false;

// 벨만포드 실행 함수
void bellman_ford() {

    for (int i = 1; i <= n; i++) { 
        d[i] = INF; 
    }

    d[1] = 0;

    // n-1번 반복 적용한다(사진 참고).
    for (int i = 1; i <= n - 1; i++) {
        for (int j = 0; j < m; j++) {

            int startN = a[j].first.first;
            int endN = a[j].first.second;
            int dist = a[j].second;
            
            // 방문하지 않은 상태라면, 넘어간다.
            if (d[startN] == INF) { continue;}
            if (d[endN] > d[startN] + dist) {
                d[endN] = d[startN] + dist;
            }
        }
    }

    // 한 번 더 사용하였을 때, 갱신된다면 그 부분은 음의 사이클이 존재하는 부분이다. 
    음의 사이클이 존재하는 순간 무의미해지는 것으로 볼 수 있다.
        for (int i = 0; i < m; i++) {

            int startN = a[i].first.first;
            int endN = a[i].first.second;
            int dist = a[i].second;

            if (d[startN] == INF) { continue;}

            // 갱신된다면 mCycle이 존재한다는 것이 된다.
            if (d[endN] > d[startN] + dist) {
                mCycle = true;
            }
        }
 }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m;
   
    for (int i = 0; i < m; i++) {
        int start, end, cost;
        cin >> start >> end >> cost;
        a.push_back(make_pair(make_pair(start, end), cost));
    }


    bellman_ford();

    // 음수 사이클이 나오면 무의미해진다.
    if (mCycle == true) {
        cout << -1 << "\n";
    }
    else {
        // 1번 도시에서 (2~n)번째 도시로 가는 경우를 모두 출력한다.
        // 방문하지 않은 (끊겨있는) 부분에 대해서는 -1을 출력한다.
        for (int i = 2; i <= n; i++) {
            if (d[i] == INF) { cout << -1 << "\n"; }
            else { cout << d[i] << "\n"; }
        }
    }
    return 0;
}

참고 자료 : https://yabmoons.tistory.com/365