(라이님 블로그 대회 알고리즘 따라잡기 17) 벨만 포드 알고리즘(Bellman-Ford Algorithm)

https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220796963742&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList

벨만 포드 알고리즘(Bellman-Ford Algorithm) (수정: 2020-07-10)

 

다익스트라 알고리즘에 이어 거리 구하는 알고리즘 2탄! 

Bellman-Ford Algorithm은 음의 거리에 대해서도 사용이 가능하기 때문에 타임머신이나 웜홀 문제에서 유용하다!

 

시간복잡도는 O(VE)이고, 음의 cycle이 생기는지 여부가 중요할 수 있다. 음의 거리에서 오버플로우가 날 수 있으니 dist를 vector<int>가 아닌 vector<long long>으로 설정해줘야 하는 것도 잊지 말기!

 

아래는 라이님의 알고리즘을 gpt에게 살짝 수정을 부탁한 것!!!

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
typedef pair<int, int> P;

int main() {
    int N, M;
    cin >> N >> M;
    vector<P> adj[500];
    vector<long long> dist(N, INT_MAX);

    for (int i = 0; i < M; i++) {
        int A, B, C;
        cin >> A >> B >> C;
        adj[A - 1].emplace_back(B - 1, C);
    }

    dist[0] = 0;
    bool minusCycle = false;

    for (int i = 0; i < N; i++) { // (N-1) + 1번의 루프. 마지막은 음의 싸이클 존재 여부 확인용
        for (int j = 0; j < N; j++) {
            for (auto& edge : adj[j]) {
                int next = edge.first, d = edge.second;
                if (dist[j] != INT_MAX && dist[next] > dist[j] + d) {
                    dist[next] = dist[j] + d ;
                    if (i == N - 1) minusCycle = true;
                }
            }
        }
    }

    if (minusCycle) {
        cout << -1 << endl;
    }
    else {
        for (int i = 1; i < N; i++) {
            if (dist[i] == INT_MAX) cout << -1 << endl;
            else cout << dist[i] << endl;
        }
    }

    return 0;
}