SPFA (Shortest Path Faster Algorithm)

SPFA 는 벨만 포드 알고리즘의 확장 알고리즘이다.

벨만 포드에서 1 단계의 완화를 시킬때, 간선들을 임의로 골라서 완화시켰기 때문에 비효율적인 면이 있었다.

어떠한 정점의 최단거리가 감소하지 않았다면, 그 정점에서 시작하는 간선들을 완화시키는 것은 의미가 없다.

이를 이용하면, 어떠한 정점이 완화되어 최단거리가 바뀌었다면, 그 정점으로부터 시작하는 간선들만 완화해주면 된다.

 

이는 BFS 와 비슷하게 큐를 이용하여 구현할 수 있다.

처음에 시작점을 큐에 넣어논 후, 그 정점으로부터 완화를 시키고, 또 성공적으로 완화된 정점들에 대해서 다시 큐에 넣어준다.

이 방법도 벨만포드와 마찬가지로 $O(VE)$ 이다.

 

하지만, 만약 어떤 정점 v가 이미 큐에 들어가 있고, 아직 큐에서 나오지 않은 상태인데, 지금 이 정점 v를 큐에 다시 넣어줄 필요가 있을까?

값을 완화만 시켜주고, 이미 한번 들어가 있기 때문에 다시 큐에 넣어줄 필요가 없음을 알 수 있다.

따라서 inque 라는 큐에 그 원소가 들어있는가를 저장하는 배열을 사용하여 필요없는 정점들을 다시 큐에 넣어주는 낭비는 하지 않도록 한다.

 

이렇게 최적화를 해주면, 최악의 경우의 시간복잡도 $O(VE)$, 평균 시간복잡도 $O(E)$ 가 나온다.

 

음수사이클 판별 방법도 벨만 포드와 유사하다.

벨만 포드에서는 전체 완화의 단계가 N번째에서 완화되는 것이 있으면 음수 사이클이 있다고 판별하였는데, 여기서도, 어떠한 정점이 큐에 N번 이상 들어가면 음수사이클이 있다고 생각할 수 있다.

따라서 완화를 시킬 때, 큐에 들어간 횟수를 저장하는 배열을 만들고, 그 배열의 값이 N이상이면 종료하면 된다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const int INF = 987654321;

int n, m, dist[MAXN+10], cnt[MAXN+10], par[MAXN+10];
vector<pii> adj[MAXN];
bool inque[MAXN+10], negcycle;

int main()
{
    int i, j;

    scanf("%d%d", &n, &m);
    for(i=1; i<=m; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        adj[u].push_back({v, w});
    }

    queue<int> Q;
    for(i=1; i<=n; i++) dist[i]=INF;
    dist[1]=0; Q.push(1); inque[1]=true; cnt[1]++; par[1]=1;

    while(!Q.empty())
    {
        int now=Q.front();
        Q.pop(); inque[now]=false;

        for(auto nxt : adj[now])
        {
            if(dist[now]+nxt.second<dist[nxt.first])
            {
                dist[nxt.first]=dist[now]+nxt.second;
                par[nxt.first]=now;
                if(cnt[nxt.first]==n) negcycle=true;
                if(!inque[nxt.first])
                {
                    cnt[nxt.first]++;
                    Q.push(nxt.first);
                    inque[nxt.first]=true;
                }
            }
        }
    }

    if(negcycle) return !printf("-1");
    for(i=2; i<=n; i++)
    {
        if(dist[i]!=INF) printf("%d\n", cnt[i]);
        else printf("-1\n");
    }
}