백준 11657 c++ (SPFA)

https://www.acmicpc.net/problem/11657

(SPFA 공부하고 적용해봤는데 타입 잘 못 잡기 + INF 케이스 오버플로우 방지 안함에 의해 수없이 틀려버렸다....)

 

SPFA 알고리즘은 벨만-포드 알고리즘의 응용으로 벨만-포드 알고리즘이 모든 정점에 대해서 거리를 업데이트하는 것 대신, 

거리 업데이트되는 노드를 대상으로만 알고리즘을 진행하는 방식이다. 

알고리즘을 진행할 노드를 큐로 관리하며, 큐에 해당 노드가 존재하는 지 체크하는 배열을 별도로 두어 중복 계산을 방지한다. 

 

벨만-포드 알고리즘이 복잡도가 O(VE) 이지만, SPFA는 dense 그래프가 아니면 O(V+E) 수준이므로, 벨만 포드보다 빠르게 음수가 있는 가중치에서도 최단 거리 계산에 접목할 수 있다.

그리고 큐에 전체 노드 개수만큼 추가된 경우 (즉, 거리 업데이트 및 알고리즘 수행을 위해 n번 해당 노드를 방문) cycle이 발생한 경우이므로 사이클 체크 또한 가능하다. 

 

위 문제에 대한 코드는 아래와 같다. 

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int n, m; // n <= 500
int from, to; 
long long cost; // 문제 상 a,b,c 
long long INF = 9223372036854775807; // 무한대

vector<pair<int, long long>> graph[501]; // [i = from] : {to, val}
vector<bool> inQueue; // 해당 노드 큐에 있는 지 유무 체크
vector<long long> dist; // 시작 노드에서 해당 노드까지 최단 거리
vector<int> cycleCount; // 무한 루프 체크용

void init() {
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        cin >> from >> to >> cost;
        graph[from].push_back({to, cost});
    }

    inQueue.resize(n + 1, false);
    dist.resize(n + 1, INF);
    cycleCount.resize(n + 1, 0);
}

// SPFA
// 벨만 포드에서 모든 정점 기준으로 거리 업데이트하는 것 대신 
// 갱신된 노드 대상으로만 거리 업데이트 진행
// 특정 노드가 전체 노드 개수만큼 큐에 추가되면 한 바퀴 다 돌고도 갱신되는 것이므로 무한 루프 지점임
// 복잡도 : worst O(V*E), 대부분 O(V+E)

int SPFA() {
    queue<int> q;

    q.push(1); // 문제 상 시작 1번 노드 
    inQueue[1] = true;
    dist[1] = 0;
    cycleCount[1]++;

    while(!q.empty()) {
        int cur = q.front();
        q.pop();

        inQueue[cur] = false;
        long long d = dist[cur];

        // 갱신 안 된 노드 
        if(d == INF) continue;

        for(int i = 0; i < graph[cur].size(); i++) {
            int next = graph[cur][i].first;
            long long cost = graph[cur][i].second;

            long long toNext = dist[next]; // 시작점에서 next까지 현재 계산된 거리
            long long nd = d + cost; // cur 거쳐서 갈 때 거리

            // 거리 업데이트 하는 경우 
            if(toNext > nd) {
                // 거리 업데이트 
                dist[next] = nd;

                // 큐에 없는 경우 
                if(inQueue[next] == false) {
                    // 큐에 추가
                    q.push(next);
                    inQueue[next] = true; 
                    // 카운트 추가
                    cycleCount[next]++;

                    // cycle 발생하는 경우
                    if(cycleCount[next] >= n) {
                        return -1;
                    }
                }
            }
        }
    }

    return 0;
}

int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    init();
    
    int res = SPFA();
    if(res == -1) {
        cout << -1 << '\n'; 
        return 0;
    }

    for(int i = 2; i <= n; i++) {
        // 해당 지점까지 못 가는 경우 
        if(dist[i] == INF) cout << -1 << '\n';
        else cout << dist[i] << '\n';
    }

    return 0;
}