118. Shortest Path Faster Algorithm

Shortest Path Faster Algorithm(SPFA)은 벨만-포드 알고리즘을 약간 변형한 것으로 간선을 확인할 때 $d_v$의 값이 변하지 않았을 경우 그 정점과 인접한 정점을 다음 차례에 바로 확인할 필요가 없다는 성질을 이용한다. 작동 방식은 다음과 같다.

    1. 시작 정점은 $k$, 정점 $k$로부터 정점 $i$까지의 최단 거리를 $d_i$라고 한다.

    2. 정점 $x$에서 정점 $y$로 가는 가중치 $z$인 간선이 존재할 때 $w(x, y) = z$라고 한다.

    3. $d_k$는 $0$, 나머지 $d_i$는 모두 $\infty$로 초기화한다.

    4. 빈 큐에 정점 $k$를 추가한다.

    5. 큐에서 정점 하나를 뺀다. 이 정점을 $u$라고 하자.

    6. $u$에서 나가는 간선이 존재하는 각각의 정점 $v$에 대해 $d_u + w(u, v) < d_v$라면 $d_v$를 $d_u + w(u, v)$로 바꾸고 큐에 $v$가 존재하지 않을 경우 큐에 $v$를 추가한다.

    7. 큐가 빈 경우 실행을 종료한다. 그렇지 않은 경우 5번으로 돌아간다.

 

어떻게 보면 다익스트라 알고리즘과도 유사하다. 다만 다익스트라 알고리즘에서는 우선순위 큐를, SPFA에서는 큐를 사용한다는 점과 SPFA에서는 큐에 포함된 원소의 개수가 항상 정점의 수 $n$을 넘지 않는다는 점 등이 서로 다르다. SPFA 알고리즘의 시간복잡도는 최악의 경우 $O(nm)$이지만 실제로는 더 빠른 경우가 많고, 평균 시간복잡도가 $O(m)$임이 알려져 있다.

 

구현은 다음과 같다. $w$ 배열은 큐에 각각의 정점이 존재하는지를 체크한다.

#import<bits/stdc++.h>
using namespace std;
int d[1005], w[1005];
vector<pair<int, int>>e[1005];
queue<int>Q;
int main()
{
    int k, m, n, x, y, z;
    cin >> n >> m >> k;
    for(int i = 1; i <= m; i++)
    {
        cin >> x >> y >> z;
        e[x].push_back({y, z});
    }
    fill(d + 1, d + n + 1, 1 << 30);
    d[k] = 0;
    for(Q.push(k); Q.size(); Q.pop())
    {
        int u = Q.front();
        w[u] = 0;
        for(auto &p: e[u])
        {
            int v = p.first;
            if(d[u] + p.second < d[v])
            {
                d[v] = d[u] + p.second;
                if(!w[v])
                {
                    Q.push(v);
                    w[v] = 1;
                }
            }
        }
    }
}

그래프에 시작 정점에서 도달할 수 있는 음수 사이클이 존재할 경우 실행이 안 끝날 수도 있으므로 주의해야 한다. 다만 시작 정점에서 도달할 수 있는 음수 사이클을 감지하는 것은 가능한데, 한 정점이 큐에 $n$번 이상 들어가는 등의 상황이 발생할 경우 음수 사이클이 존재한다고 할 수 있다.

 

SPFA는 나중에 MCMF를 다룰 때 다시 등장하며, 실제로도 벨만-포드 알고리즘이나 SPFA가 단독으로 쓰이기보다는 MCMF 문제를 풀기 위해 사용하는 경우가 많다.