SPFA (Shortest Path Faster Algorithm)

SPFA는 그래프에서 최단 경로를 구하는 알고리즘으로, 중요하게 사용되는 것은 MCMF를 구현할 때이다. 우선 SPFA에 대해 알아보기에 앞서 다른 최단 경로 알고리즘들에 대해 간단하게 살펴보자.

 

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

 

이제 SPFA 알고리즘에 대해 알아보자. SPFA 알고리즘은 벨만-포드 알고리즘의 성능을 향상시킨 것으로, 음수 간선이 있는 그래프에서 최단경로를 빠르게 구할 수 있다. 최악의 시간복잡도는 여전히 $O(VE)$이지만 실제로는 $O(V+E)$ 정도로 동작한다. 벨만-포드 알고리즘에서는 모든 간선들을 살펴보며 relax(최단거리를 갱신)하는 과정을 $V-1$번 반복하였다. SPFA 알고리즘에서는 단순히 모든 간선을 반복하며 relax시키는 것이 아니라, 갱신된 점들에 대해 연결된 간선들만 relax시킨다. 구체적으로는 relax 시킬 간선들의 queue가 있고, 갱신된 점과 연결된 간선들이 queue에 없다면 넣는 것이다. 이를 반복하면 최단경로 계산이 완료되었을 때 queue가 비게 된다. 최악의 시간복잡도는 $O(VE)$이다. 만약 음수 사이클이 있다면 한 간선이 $V$번 이상 relax되게 된다.

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

 

아래는 SPFA의 코드이다. (백준 타임머신 문제)

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

typedef pair<int, int> pii;

const int MAXN = 510;
const int MAXM = 6010;
const int INF = 1 << 30;

#define fi first
#define se second
#define eb emplace_back

vector<pii> ed[MAXN];
int d[MAXN];
bool inq[MAXN];			// queue에 해당 정점이 들어가있는지 여부
int cnt[MAXN];

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N, M;

	cin >> N >> M;
	for(int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		ed[a].eb(b, c);
	}

	for(int i = 2; i <= N; i++) d[i] = INF;
	queue<int> q;
	q.push(1);
	inq[1] = true;
	while(!q.empty()) {
		int t = q.front();
		q.pop();
		inq[t] = false;
		if(++cnt[t] >= N || d[t] < -INF) {	// 음수 사이클
			cout << "-1\n";
			return 0;
		}
		for(auto a : ed[t]) if(d[t] + a.se < d[a.fi]) {
			d[a.fi] = d[t] + a.se;
			if(!inq[a.fi]) {		// queue에 없을 경우 추가
				q.push(a.fi);
				inq[a.fi] = true;
			}
		}
	}

	for(int i = 2; i <= N; i++) cout << (d[i] == INF ? -1 : d[i]) << "\n";
	return 0;
}

 

아래 내용을 통해 공부하였다.

https://www.crocus.co.kr/1089