언제 사용할까?
SPFA(Shortest Path Faster Algorithm) 알고리즘은 그래프에서 가중치가 있는 단일 시작점 최단 경로 문제를 해결하는 데 사용됩니다. 벨만-포드 알고리즘과 유사하지만, 특히 음수 가중치가 있는 간선이 존재하는 그래프에서 효율적으로 작동하도록 최적화된 알고리즘입니다.
- 그럼 멀티 소스 문제에는 사용할 수 없나?
SPFA 알고리즘은 단일 시작점 최단 경로 (Single-Source Shortest Path, SSSP) 알고리즘이기 때문에, 기본적으로 멀티 소스 (Multi-Source) 문제에는 직접적으로 적용할 수 없습니다. 즉, 여러 개의 시작점에서 다른 모든 정점까지의 최단 경로를 동시에 구하는 데는 적합하지 않습니다.
- 음수 가중치가 없을 때 다익스트라 보다 성능이 떨어지니 사용하지 않을 것
성능
평균적인 경우: SPFA는 O(E) 에 가까운 시간 복잡도를 보이며, 벨만-포드의 O(VE) 보다 빠릅니다. 특히 희소 그래프(Sparse Graph) 에서 큰 성능 차이를 보입니다.
최악의 경우: SPFA는 O(VE) 의 시간 복잡도를 가지며, 이는 벨만-포드와 동일합니다. 드물게 특정 입력에 대해 매우 느리게 동작할 수 있습니다.
음수 사이클 감지: SPFA는 정점이 큐에 들어간 횟수를 기준으로 감지(일반적으로 더 빠름), 벨만-포드는 |V|번째 반복에서도 거리 갱신 여부로 감지합니다.
다익스트라와 비슷한 것 같은데, 왜 우선순위 큐를 사용하지 않는가
SPFA는 “언제 어느 정점을 꺼내서 확인할지” 를 다익스트라처럼 정교하게 관리하지 않고, 단순히 ‘갱신이 발생하면 큐에 넣는다’는 규칙만 있습니다. 그래서 우선순위 큐가 필요한 상황이 아니라 일반 큐로도 충분합니다.
음수 가중치 때문입니다. 음수 가중치가 있으면, 현재까지 알려진 최단 거리가 가장 짧은 정점을 선택하더라도, 나중에 더 짧은 경로가 발견될 수 있습니다.
SPFA는 "최단 거리"만을 우선순위로 정점을 선택하는 알고리즘이 아니기 때문입니다.
큐를 사용해 최단 거리가 갱신된 정점을 관리하고, 이를 통해 음수 가중치가 있는 그래프에서도 효율적으로 최단 경로를 찾을 수 있습니다.
구현
int[] count 배열은 음수 사이클을 방지하기 위해 존재
int[] inQueue는 Queue내부에 정점이 중복으로 들어가지 않게 하기위해 사용됩니다.
일반적으로 사용되는 isVisited와는 다른 의미를 가집니다.
SPFA에서는 하나의 정점도 여러번 방문할 수 있습니다.
import java.util.*;
class Edge {
int to;
int weight;
public Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
public class SPFA {
static final int INF = Integer.MAX_VALUE;
public static int[] spfa(int start, int numVertices, List<List<Edge>> adjList) {
int[] dist = new int[numVertices + 1]; // 1-based indexing
Arrays.fill(dist, INF);
dist[start] = 0;
Queue<Integer> queue = new LinkedList<>();
queue.offer(start);
boolean[] inQueue = new boolean[numVertices + 1]; // 1-based indexing
inQueue[start] = true;
int[] count = new int[numVertices + 1]; // 1-based indexing
count[start] = 1;
while (!queue.isEmpty()) {
int u = queue.poll();
inQueue[u] = false;
for (Edge edge : adjList.get(u)) {
int v = edge.to;
int w = edge.weight;
if (dist[u] != INF && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
if (!inQueue[v]) {
queue.offer(v);
inQueue[v] = true;
count[v]++;
// 음수 사이클 감지
if (count[v] > numVertices) {
System.out.println("Negative cycle detected!");
return null; // 또는 예외를 던질 수 있습니다.
}
}
}
}
}
return dist;
}
public static void main(String[] args) {
int numVertices = 5;
List<List<Edge>> adjList = new ArrayList<>();
for (int i = 0; i <= numVertices; i++) {
adjList.add(new ArrayList<>());
}
// 간선 추가 (예시)
adjList.get(1).add(new Edge(2, -1));
adjList.get(1).add(new Edge(3, 4));
adjList.get(2).add(new Edge(3, 3));
adjList.get(2).add(new Edge(4, 2));
adjList.get(2).add(new Edge(5, 2));
adjList.get(4).add(new Edge(2, 1));
adjList.get(4).add(new Edge(3, 5));
adjList.get(5).add(new Edge(4, -3));
int startVertex = 1;
int[] shortestDistances = spfa(startVertex, numVertices, adjList);
if (shortestDistances != null) {
System.out.println("Shortest distances from vertex " + startVertex + ":");
for (int i = 1; i <= numVertices; i++) {
System.out.println("To vertex " + i + ": " + (shortestDistances[i] == INF ? "INF" : shortestDistances[i]));
}
}
}
}
