Shortest Path Faster Algorithm(SPFA)

이 게시글에서는 벨만 포드 알고리즘의 평균 시간 복잡도를 크게 개선한 SPFA의 구현법과 특징을 알아본다.

SPFA의 사용 의의

SPFA의 시간 복잡도는 벨만 포드와 동일하게 $O(VE)$이지만 SPFA 저격 데이터가 없는 경우 $O(V + E)$의 성능을 낸다고 알려져 있다.

 

따라서 채점 데이터가 약하다고 추정되는 문제에서 최단 경로를 찾을 때는 SPFA의 사용을 고려할 수 있다.

 

단, 저격 데이터가 있는 경우 SPFA의 큐 사용에서 발생하는 상수 시간이 더 크기 때문에 벨만 포드보다 느린 퍼포먼스를 보여준다는 것을 유의해야 한다.

 

SPFA는 MCMF의 구현에 많이 이용하므로 플로우와 관련된 알고리즘을 배우기 전에 꼭 숙지해야 하는 알고리즘이다.

C++ 구현

SPFA는 큐를 이용해서 BFS와 유사하게 작동한다.

#define NODE_MAX 1001
vector<vector<pair<int, int>>> graph;
long long dist[NODE_MAX];
int node_cnt[NODE_MAX];
bool inq[NODE_MAX];

bool spfa(int start, int limit) {
  queue<int> q;
  fill(dist, dist + NODE_MAX, 1e18);
  dist[start] = 0;
  inq[start] = 1;
  ++node_cnt[start];
  q.push(start);
  while (q.size()) {
    int cur = q.front();
    q.pop();
    inq[cur] = 0;
    for (auto &node: graph[cur]) {
      int nv = node.first, w = node.second;
      if (dist[cur] + w < dist[nv]) {
        dist[nv] = dist[cur] + w;
        if (!inq[nv]) {
          if (++node_cnt[nv] >= limit) return false;
          inq[nv] = 1;
          q.push(nv);
        }
      }
    }
  }
  return true;
}

 

기존 벨만포드와는 다르게 완화가 이루어진 노드만을 큐에 넣어 완화가 이루어지지 않을 때까지 인접 노드를 탐색한다.

 

완화된 노드를 큐에 넣을 때는 inq 배열에서 어떤 노드가 큐에 들어있는지 관리하여 큐에 없는 노드만 넣어 노드의 중복을 방지한다.

 

node_cnt 배열은 각 노드가 몇 번 큐에 들어갔는지 관리하는 배열이다. 벨만 포드 알고리즘은 n번 이상 완화가 이루어지면 음수 사이클이 존재한다고 판단할 수 있었는데, SPFA에서는 어떤 노드가 n번 이상 큐에 들어가게 되었는지가 음수 사이클의 판단 조건이 된다.

 

n번 이상 큐에 들어가면 false, 그렇지 않고 과정을 완료했으면 true를 리턴해서 음수 사이클의 여부를 확인할 수 있다.

 

다음은 백준 - 타임머신을 SPFA로 해결한 코드이다.

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

#define NODE_MAX 501
vector<vector<pii>> graph;
long long dist[NODE_MAX];
int node_cnt[NODE_MAX];
bool inq[NODE_MAX];

bool spfa(int start, int limit) {
  queue<int> q;
  fill(dist, dist + NODE_MAX, 1e18);
  dist[start] = 0;
  inq[start] = 1;
  ++node_cnt[start];
  q.push(start);
  while (q.size()) {
    int cur = q.front();
    q.pop();
    inq[cur] = 0;
    for (auto &node: graph[cur]) {
      int nv = node.first, w = node.second;
      if (dist[cur] + w < dist[nv]) {
        dist[nv] = dist[cur] + w;
        if (!inq[nv]) {
          if (++node_cnt[nv] >= limit) return false;
          inq[nv] = 1;
          q.push(nv);
        }
      }
    }
  }
  return true;
}

int n, m;

void solve()
{
  cin >> n >> m;
  graph.resize(n + 1);

  for (int i = 0; i < m; ++i)
  {
    int go, to, fee;
    cin >> go >> to >> fee;
    graph[go].push_back({to, fee});
  }

  bool res = spfa(1, n);

  if (!res)
  {
    cout << -1;
    return;
  }

  for (int i = 2; i <= n; ++i)
    cout << (dist[i] != 1e18 ? dist[i] : -1) << '\n';
}

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

  solve();
}

SPFA의 최적화 기법 Small Label First(SLF)

음수 사이클이 없는 가중치 그래프에 대해 최적화 기법을 적용하면 저격 데이터에 대해 어느 정도 대응할 수 있다고 한다.

 

그 방법 중 하나가 Small Label First(이하 SLF)이다.

 

SLF는 큐 대신 덱을 사용하여 0-1 BFS와 비슷하게 값이 큰 노드를 덱의 뒤로 보내버리는 전략을 적용한다.

if (dist[dq.front()] > dist[dq.back()])
  dq.push_back(dq.front()), dq.pop_front();

 

그러나 백준 온라인 저지에서 최적화 기법을 저격하는 데이터가 이미 존재하는 상황이고, 최적화를 적용하면 더이상 음수 사이클이 있는 그래프에서 적용할 수 없다는 문제가 발생하므로 CP에서는 최적화 기법을 적용하지 않는 게 좋을 것이다.

 

백준 - 타임머신 문제는 SLF SPFA로 풀 수 없다.

 

지금까지 SPFA의 특징과 그 구현을 알아보았다. SPFA는 MCMF의 구현에 필수이고 weak TC에 대해 AC를 노려볼 수 있는 알고리즘이니 알아두면 재미를 볼 수 있을 것이다.