SPFA(Shortest Path Faster Algorithm)

SPFA, Shortest Path Faster Algorithm

SPFA는 최단 경로 알고리즘으로, MCMF(Mininum Cost Maximun Flow)를 구현할 때 사용된다.

BFS와 벨만포드 알고리즘을 섞은 것과 비슷하다. 모든 간선의 가중치가 같은 그래프에서 SPFA를 수행하면 BFS와 똑같이 동작한다.

 

최단 경로 알고리즘

다익스트라: O(ElogV)로 동작하지만, 음수 간선은 처리 불가

플로이드-와셜: 음수 간선은 처리 가능하지만, 모든 정점들간의 거리를 구하는데 사용되고 O(V^3)으로 동작

벨만-포드: 음수 간선 처리 가능, O(VE)

 

음수간선이 포함된 사이클이 존재한다면, 비용은 점점 작아져 -INF가 된다.

해당 정점이 N번 이상 방문되었는지를 체크하여, 음수사이클의 존재 여부를 확인할 수 있다.

음수간선 최소비용을 구할 때는 음수 비용의 경우 N * M * C로 언더플로우가 발생할 수 있기 때문에 정수 범위를 잘 고려해야한다.

 

이제 MCMF(Network Flow + SPFA)문제를 풀 준비가 됬다.!

 

문제

음수간선을 포함한 최단 경로: https://www.acmicpc.net/problem/11657

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <cstring>
#include <cmath>
#include <unordered_map>
using namespace std;
int N, M;
struct Node {
    int n, cost;
};
vector<Node> graph[501];
queue<int> q;
int check[501];
long long answer[501];
int visitedCnt[501];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    int a, b, c;
    for (int i = 0; i < M; ++i)
    {
        cin >> a >> b >> c;
        graph[a].push_back({ b, c });
    }
    for (int i = 1; i <= N; ++i) answer[i] = 1987654321;
    q.push(1);
    check[1] = 1;
    answer[1] = 0;
    int cnt = 0;
    while (!q.empty())
    {
        int qSize = q.size();
        for (int i = 0; i < qSize; ++i)
        {
            int now = q.front();
            q.pop();
            check[now] = 0;
            visitedCnt[now] ++;
            if (visitedCnt[now] >= N) {
                // 해당 정점을 N 번 이상 방문하였다면.
                cout << -1;
                return 0;
            }

            for (int j = 0; j < graph[now].size(); ++j)
            {
                Node nxt = graph[now][j];
                long long nextCost = answer[now] + nxt.cost;
                if (nextCost >= answer[nxt.n]) continue;
                answer[nxt.n] = nextCost;
                if (check[nxt.n] == 0) {
                    check[nxt.n] = 1;
                    q.push(nxt.n);
                }
            }
        }
    }

    for (int i = 2; i <= N; ++i)
        cout << (answer[i] > 1987654000 ? -1 : answer[i]) << "\n";
    return 0;
}