Algorithm in A..Z - SPFA

개념

Short Path Faster Algorithm의 약어로 가장 빠른 경로를 찾는 알고리즘이다.

다익스트라 알고리즘은 음수인 간선이 존재할 때 사용할 수 없고, 벨만-포드 알고리즘보다 효율이 좋기 때문에 MCMF 알고리즘에서 많이 사용한다.

---

작동원리

isIn => 덱에 해당 정점이 있는지 확인하는 배열, 큐에 중복으로 값을 넣는 것을 방지

count => 업데이트된 횟수를 저장하는 배열, CYCLE을 확인할 수 있다.(벨만-포드와 같은 개념)

 

1. 시작 정점을 덱에 넣고 count, isIn, distance를 업데이트한다.

2. 덱에서 POP FRONT하고 isIn을 false로 업데이트한다.

3. 현재 정점에서 갈 수 있는 정점중 distance를 업데이트 할 수 있는 정점이 있으면 distance를 업데이트한다.

4. count가 n이상이면 CYCLE을 체크하고 2로 간다.

5. isIn으로 덱에 있는지 확인한다.

6. 덱에 없으면 isIn, count를 업데이트한다.

7. 덱이 비었거나, FRONT의 distance가 정점보다 크면 PUSH FRONT하고 그렇지 않으면 PUSH BACK한다.

=> SPFA를 최적화 하는 방법

8. 2 ~ 7을 덱이 EMPTY일 때까지 반복한다.

---

시간 복잡도

최선 O(V)

최악 O(VE)

---

문제

10360 The Mountain of Gold?

www.acmicpc.net/problem/10360

10360번: The Mountain of Gold?

---

코드

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

class Edge {
public:
    int vertex;
    long long distance;

    explicit Edge(int vertex = 0, long long distance = 0L) : vertex(vertex), distance(distance) {

    }
};

int main() {
   ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

   int t;
   cin >> t;
   for (int test = 1;test <= t;++test) {
       int n, m;
       cin >> n >> m;

       vector<vector<Edge>> map(n), rmap(n);
       while (m--) {
           int source, destination, distance;
           cin >> source >> destination >> distance;

           map[source].emplace_back(destination, distance);
           rmap[destination].emplace_back(source, distance);
       }

       queue<int> que;
       vector<bool> canGoBack(n, false);

       que.emplace(0);
       canGoBack[0] = true;
       while (!que.empty()) {
           auto now = que.front(); que.pop();

           for (auto &next : rmap[now]) {
               if (!canGoBack[next.vertex]) {
                   que.emplace(next.vertex);
                   canGoBack[next.vertex] = true;
               }
           }
       }

       deque<int> deque;
       vector<int> count(n, 0);
       vector<bool> isIn(n, false);
       vector<long long> distance(n, INT64_MAX);

       deque.emplace_back(0);
       count[0]++;
       isIn[0] = true;
       distance[0] = 0;

       while (!deque.empty()) {
           auto now = deque.front();deque.pop_front();

           isIn[now] = false;
           for (auto &next : map[now]) {
               if (distance[next.vertex] > distance[now] + next.distance) {
                   distance[next.vertex] = distance[now] + next.distance;
                   if (count[next.vertex] == n) {
                       continue;
                   }

                   if (!isIn[next.vertex]) {
                       isIn[next.vertex] = true;
                       count[next.vertex]++;
                       if (deque.empty() || distance[deque.front()] > distance[next.vertex]) {
                           deque.emplace_front(next.vertex);
                       } else {
                           deque.emplace_back(next.vertex);
                       }
                   }
               }
           }
       }

       bool isFounded = false;
       for (int i = 1;i <=n; ++i) {
//           cout << i << " : " << count[i] << ", " << canGoBack[i] << endl;

           if (count[i] >= n && canGoBack[i]) {
               isFounded = true;
               break;
           }
       }

       cout << "Case #" << test << ": " << (isFounded ? "" : "not ") << "possible" << "\n";
   }
}