SPFA (Shortest Path Faster Algorithm)

SPFA알고리즘은 벨만포드 알고리즘의 개선판으로, 

벨만-포드 알고리즘이 정점의 개수가 V일때, 모든 정점을 V-1번 갱신하는데 비해, 

SPFA는 queue를 사용해서, 시작점과 연관있는 정점만 갱신해 나가는 아이디어

 

아래는 직접 구현해 본건데 백준11657문제의 답안이기도 하다.

#include <bits/stdc++.h>
using namespace std;
 
const int INF = INT_MAX / 4;
struct node { int v, w; };
vector<int> SPFA(int max_v, int start_v, vector<vector<node>>&adj_list) {
    vector<int> min_dist(max_v + 1, INF);
    min_dist[start_v] = 0;
    queue<node> q; q.push({ start_v,0 });
    queue<int> qn; qn.push(0);
    while (q.size()) {
        node n = q.front(); q.pop();
        int nn = qn.front(); qn.pop();
        if (nn >= max_v) { printf("-1\n"); exit(0); }//네거티브 사이클
 
        //이 부분, 아래 for문 안쪽이랑 중복같기도 해보이지만 없으면 TLE난다.
        if (min_dist[n.v] < n.w) continue;
        min_dist[n.v] = n.w;
 
        for (node adj : adj_list[n.v]) {
            //최소값으로 업데이트
            if (min_dist[adj.v] <= adj.w + n.w) continue;
            min_dist[adj.v] = adj.w + n.w;
            q.push({ adj.v, adj.w + n.w }), qn.push(nn + 1);
        }
    }
    return min_dist;
}
 
int main()
{
    int N, M; scanf("%d%d", &N, &M);
    vector<vector<node>> adj_list(N + 1);
    for (int i = 0; i < M; i++) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        adj_list[u].push_back({ v,w });
        //adj_list[v].push_back({ u,w });
    }
 
    vector<int> dist = SPFA(N, 1, adj_list);
    for (int i = 2; i <= N; i++) {
        printf("%d\n", dist[i] == INF ? -1 : dist[i]);
    }
    return 0;
}

 

근데 제출해본 결과, 스피드업이 없었다는 문제가? 복잡도로는 벨만포드와 같기도 하고...

근데 보면 볼수록 신기한점은 우선순위큐만 없고, for문안에 continue로직이 추가됐을뿐이지 다익스트라랑 소스코드가 거의 동일하다는 점이다.

그래도 네거티브 사이클을 디텍트할 수 있는건 장점

 

ChatGPT 말로는 위 코드는 SPFA는 아니라는데 ㅋㅋ 나중에 시간날때 검토해보자.

is it SPFA?
No, it is not SPFA (Shortest Path Faster Algorithm). SPFA is also a single-source shortest path algorithm, similar to Bellman-Ford, but it uses a queue to keep track of the current node and its distance from the starting node, whereas Bellman-Ford uses a simple loop. The implementation you provided is the Bellman-Ford algorithm, as it uses queue, it does not check negative-weighted edges and it uses for loop, which is the characteristic of Bellman-Ford algorithm, also it uses the continue in order to check whether the current node is visited or not, which is another characteristic of Bellman-Ford algorithm.