SPFA (Shortest Path Faster Algorithm)

개념)

다익스트라 알고리즘은 O(ElogV)로 동작하며 (이론적으로는 O(E+VlogV) 음수 간선은 처리할 수 없다. 일반적으로 가장 많이 사용된다. 플로이드-와셜 알고리즘은 O(V3)으로 동작하며, 모든 정점들간의 거리를 모두 구한다는 특징이 있다. 음수 간선이 있어도 잘 동작하며 음수 사이클의 여부를 판단할 수 있다. 벨만-포드 알고리즘은 O(VE)이며 음수 간선이 있어도 잘 동작하고, 음수 사이클의 여부를 판단할 수 있다.

 

이제 SPFA 알고리즘에 대해 알아보자. SPFA 알고리즘은 벨만-포드 알고리즘의 성능을 향상시킨 것으로, 음수 간선이 있는 그래프에서 최단경로를 빠르게 구할 수 있다. 최악의 시간복잡도는 여전히 O(VE)이지만 실제로는 O(V+E) 정도로 동작한다. 벨만-포드 알고리즘에서는 모든 간선들을 살펴보며 완화(최단거리를 갱신)하는 과정을 V−1번 반복하였다.

SPFA 알고리즘에서는 단순히 모든 간선을 반복하며 완화시키는 것이 아니라, 갱신된 점들에 대해 연결된 간선들만 완화시킨다. 구체적으로는 완화시킬 간선들의 queue가 있고, 갱신된 점과 연결된 간선들이 queue에 없다면 넣는 것이다. 이를 반복하면 최단경로 계산이 완료되었을 때 queue가 비게 된다. 최악의 시간복잡도는 O(VE)이다. 만약 음수 사이클이 있다면 한 간선이 V번 이상 완화된다.

SPFA는 벨만포드 알고리즘과 bfs를 섞은 느낌이다. 실제로 모든 간선의 가중치가 같은 그래프에서 SPFA를 실행하면 bfs와 똑같이 동작한다. 혹은 다익스트라에서 priority_queue 대신 queue를 사용했다고 생각할 수도 있다. 

구현)

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

#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;
}

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에서는 최적화 기법을 적용하지 않는 게 좋을 것이다.

 

 

SPFA (Shortest Path Faster Algorithm) (tistory.com)

Shortest Path Faster Algorithm(SPFA) (tistory.com)