SPFA (Shortest Path Faster Algorithm)

SPFA (Shortest Path Faster Algorithm)에 대해 알아보고자 한다.

이 알고리즘은 벨만포드 알고리즘의 성능을 향상시킨 알고리즘으로써

시간 복잡도는 O(V*E)이지만 실제로는 훨씬 빨리 돌아가는 알고리즘으로 O(V+E) 혹은 O(E)라고 해도 무방하다. 

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

벨만포드와 SPFA는 같은 아이디어이지만 차이점은 

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

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

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

[11657번] 타임머신 :: https://www.acmicpc.net/problem/11657 이 문제를 통해 SPFA를 적용해보자.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83

#include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <queue>   using namespace std;   typedef pair<int, int> pii;   const int MAX_V = 502; const int INF = 987654321;   int dist[MAX_V], cost[MAX_V]; bool inQ[MAX_V];   int cycle[MAX_V];   vector<pii> adj[MAX_V];   int main() {     int n, m;     scanf("%d %d", &n, &m);       for (int i = 0; i < m; i++)     {         int from, to, val;         scanf("%d %d %d", &from, &to, &val);           adj[from].push_back({ to, val });     }       fill(dist, dist + MAX_V, INF);       queue<int> q;     dist[1] = 0;     inQ[1] = true;       q.push(1);     cycle[1]++;       while (!q.empty())     {         int here = q.front();         q.pop();           inQ[here] = false;           for (int i = 0; i < adj[here].size(); i++)         {             int next = adj[here][i].first;             int cost = adj[here][i].second;               if(dist[next] > dist[here] + cost)             {                 dist[next] = dist[here] + cost;                   if (!inQ[next])                 {                     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 ? dist[i] : -1);       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus

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

queue를 생성하고 최단거리를 나타내는 배열인 dist의 dist[1] = 0으로 맞춰주자(시작점이니).

inQ는 큐에 해당 정점이 큐에 들어있는지 확인하는 배열이다.

큐에서 꺼내면 inQ[정점] = false가 된다.

그리고 벨만포드 아이디어와 같이 dist[next] > dist[here] + cost인지 확인하고 최단거리를 갱신해준다.

이때 이미 큐에 들어가있지 않은 정점들만 넣어준다.

음수 사이클을 확인하는 방법은 한 정점이 n번 이상 방문되면 그 정점을 포함하여 어떠한 음수 사이클이 있다는 것을 알 수 있게 된다.