SPFA (Shortest Path Faster Algorithm)

참고 및 출처 :

https://www.crocus.co.kr/1089?category=209527 [Crocus]

SPFA (Shortest Path Faster Algorithm)

1. 벨만포드 알고리즘의 성능을 향상시킨 알고리즘

2. SPFA는 음수 간선에도 문제없이 돌아가기 때문에 MCMF에서 자주 쓰인다.

3. 벨만포드는 모든 간선에 대해 업데이트를 진행하지만,

SPFA는 바뀐 정점과 연결된 간선에 대해서만 업데이트를 진행한다는 것이다.

4. 바뀐 정점은 큐를 이용해서 관리하고, 큐에 해당 정점이 있는지 없는지는 배열을 이용해서 체크한다.

활용 문제 : https://www.acmicpc.net/problem/11657

벨만포드 알고리즘으로 푼 타임머신 문제

#include <bits/stdc++.h>
 
using namespace std;
 
#define INF 987654321
 
int dist[501], inQ[501], n, m;
 
vector<pair<int, int> > v[501];
 
queue<int> q;
 
int main(void)
{
    int s, e, w;
 
    scanf("%d %d", &n, &m);
 
    for (int i = 0; i < m; i++)
    {
        scanf("%d %d %d", &s, &e, &w);
        v[s].push_back({ e, w });
    }
 
    fill(dist, dist + 501, INF);
 
    dist[1] = 0;
 
    for (int i = 0; i < n; i++) // 모든 간선
        for (int j = 1; j <= n; j++) // 현재 간선
            for (int k = 0; k < v[j].size(); k++)
            {
                int next = v[j].at(k).first;
 
                if (dist[next] > dist[j] + v[j].at(k).second && dist[j] != INF)
                {
                    if (i == n - 1) // 음수 사이클, 예제 2번
                    {
                        printf("-1\n");
                        return 0;
                    }
 
                    dist[next] = dist[j] + v[j].at(k).second;
                }
            }
 
    for (int i = 2; i <= n; i++)
        printf("%d\n", dist[i] == INF ? -1 : dist[i]);
 
    return 0;
}

SPFA

#include <bits/stdc++.h>
 
using namespace std;
 
#define INF 987654321
 
int dist[501], cycle[501], n, m;
 
bool inQ[501];
 
vector<pair<int, int> > v[501];
 
queue<int> q;
 
int main(void)
{
    int s, e, w;
 
    scanf("%d %d", &n, &m);
 
    for (int i = 0; i < m; i++)
    {
        scanf("%d %d %d", &s, &e, &w);
        v[s].push_back({ e, w });
    }
 
    fill(dist, dist + 501, INF);
 
    dist[1] = 0;
    q.push(1); // 시작 정점 및 SPFA를 위한 queue
    ++cycle[1];
 
    while (!q.empty())
    {
        int here = q.front();
 
        q.pop();
 
        inQ[here] = false;
 
        for (auto i : v[here])
        {
            int next = i.first;
            
            if (dist[next] > dist[here] + i.second && dist[here] != INF)
            {
                dist[next] = dist[here] + i.second;
 
                if (!inQ[next]) // 만약 다음 정점이 Queue에 없다면
                {
                    ++cycle[next];
 
                    if (cycle[next] >= n) // 음수 사이클
                    {
                        printf("-1\n");
                        return 0;
                    }
 
                    q.push(next);
                    inQ[next] = true;
                }
            }
        }
    }
 
    for (int i = 2; i <= n; i++)
        printf("%d\n", dist[i] == INF ? -1 : dist[i]);
 
    return 0;
}