SPFA (Shortest Path Faster Algorithm)

 

시작하기 전에

그래프에서 최단 경로를 찾는 알고리즘은 크게 세 가지가 존재한다고 알고 있었다.

 

Dijkstra

- 시작점이 존재해야 함. 그래프의 간선 가중치가 음이 아닌 정수일 때만 가능

Floyd-Warshall

- 모든 정점 쌍 사이의 최단 경로를 구할 때 사용, 음수 가중치 및 음의 사이클 판별 가능

Bellman-Ford

- 시작점이 존재해야 함. 음수 가중치 및 음의 사이클 판별 가능

 

Claude 선생님과 함께 알고리즘 복습을 하던 중에 SPFA라는 것을 접하게 되었다.

---

SPFA 또한 그래프에서 최단 경로를 찾는 알고리즘이며, 이를 알기 위해선 Bellman-Ford를 먼저 알아야 한다.

여기서는 Bellman-Ford의 원리만 간단히 설명하겠다.

Bellman-Ford

정점이 $N$개인 그래프의 어떤 최단 경로에 포함되는 간선의 개수는 최대 $N-1$개라는 사실을 이용한다.

총 $N$번의 Round를 진행하며, $i$번째 Round에서는 간선을 $i$개 사용하는 최단 경로를 갱신한다.

각 Round에서는 모든 간선을 순회하며 각 간선으로 최단 거리를 갱신시킨다.

$N$번째 Round에서 갱신이 일어났다면 음의 사이클이 존재하는 것이다.

 

Round마다 간선을 순회하고 총 $N$개의 Round를 진행하므로 간선의 개수가 $M$개라면 Bellman-Ford의 시간복잡도는 $O(NM)$이다.

SPFA

Bellman-Ford에서 진행하는 각 Round에서는 불필요한 간선의 탐색이 많을 수도 있다.

어떤 간선이 $i$번째 Round에서 최단 경로 갱신에 사용되지 못했다면, 이후의 Round에서도 사용되지 않는다.

따라서 SPFA에서는 최단 거리 갱신이 진행된 정점에서 나가는 간선들로만 Round를 진행한다.

 

시간복잡도는 여전히 $O(NM)$이지만, 평균적으로 $\Theta(N+M)$에 동작한다고 한다.

구현

위 방법의 구현을 위해서 큐를 사용한다.

최단 거리 갱신이 진행된 정점들을 큐에 넣고, 나중에 큐에서 꺼낼 때 해당 정점에서 나가는 간선들을 탐색한다.

말만 들으면 Dijkstra 혹은 BFS와 유사한 것을 알 수 있다.

 

하지만 SPFA는 큐를 사용하기 때문에 최단 거리를 우선순위로 두고 탐색하는 방식이 아니다.따라서 같은 정점이 큐에 여러 번 들어갈 수 있고, 큐에 들어간 횟수가 그 정점이 거친 Round의 수가 된다.그 수가 $N$이 되는 순간, 역시 음의 사이클이 존재한다는 것이다.

 

각 정점이 큐에 몇 번 들어갔는지 알아야 하기 때문에 int 배열로 이를 관리한다.또, 큐 내에 같은 정점이 여러 번 대기하는 것을 막기 위해 bool 배열 등으로 큐 삽입 여부를 관리한다.

 

자세한 코드는 다음과 같다.

const int INF = 1e9 + 7;

int N;	// 정점 개수
vector<vector<pair<int, int>>> graph(1000001);	// adjacent list
bool negCycle = false;

void spfa(int start) {
	vector<int> dist(N, INF);	// 최단 거리 배열
	bitset<1000001> inqueue;	// 큐 대기 여부
	vector<int> cnt(N);		// 큐 진입 횟수
	queue<int> q;

	dist[start] = 0;
	inqueue[start].flip();
	cnt[start]++;
	q.push(start);

	while (!q.empty()) {
		int cur = q.front();	q.pop();
		inqueue[cur].flip();
		for (auto [nxt, cost] : graph[cur]) {
			// 갱신 가능한 nxt 발견
			if (dist[nxt] > dist[cur] + cost) {
				dist[nxt] = dist[cur] + cost;
				// 큐에 없을 때만 삽입
				if (!inqueue[nxt]) {
					// 음의 사이클 판별
					if (++cnt[nxt] >= N) {
						negCycle = true;
						return;
					}
					inqueue[nxt].flip();
					q.push(nxt);
				}
			}
		}
	}
}