SPFA

SPFA란?

SPFA(Shortest Path Faster Algorithm)의 경우 벨만-포드 알고리즘의 성능을 향상시킨 알고리즘으로서, 방향 가중치 그래프에서 단일 출발 정점 최단 거리를 계산합니다.

음수 가중치 간선을 가지고 있은 그래프에서도 적합하지만, 최악의 시간 복잡도는 O(|V| * |E|)이기 때문에 음수 가중치 간선이 없는 그래프의 경우에는 Dijkstra’s Algorithm이 더 적합하다고 볼 수 있습니다.

벨만 포드와 SPFA는 같은 아이디어이지만 차이점은

• 벨만포드: 모든 간선에 대해 업데이트를 진행
• SPFA: 바뀐 정점과 연결된 간선에 대해서만 업데이트를 진행

바뀐 정점은 Queue를 이용해서 관리하고, 큐에 해당 정점이 있는지 없는지는 배열을 이용해서 체크합니다.

또한, 음수 사이클을 확인하는 방법은 한 정점이 n번 이상 방문되면 그 정점을 포함하여 어떤 음수 사이클이 있다는 것을 알 수 있게 되므로, int[]형 배열을 사용한다.

동작 과정

1. 출발 노드 설정
2. 최단 테이블 초기화(dist[] 배열 초기화)
3. Queue를 생성 (출발 노드의 Index를 Generic Type으로 설정 즉, Queue ), boolean[] inQueue, int[] cycle배열도 생성
4. 출발 노드 idx를 넣어주고 Queue가 빌 때까지 반복문 사용
   1. Queue에 있는 노드 index꺼내주고 해당 index를 출발 노드 index 값으로 가지는 Edge를 그래프에서 확인 (출발 노드 index = srcIdx, 도착 노드 index = dstIdx, 가중치 = cost로 가정)
   2. 해당 Edge를 꺼내서 dist[] 배열을 초기화(dist[dstIdx] > dist[srcIdx] + cost 인 경우)
   3. 최단 거리 테이블이 초기화 되는 경우 cycle[]배열에서 cycle[dstIdx]++처리 해준다.
   4. 이후 Queue에 dstIdx를 push해주면서 inQueue[dstIdx] = true 처리를 해준다.

inQueue 배열로 Queue안에 해당 정점이 들어가 있는지 확인하고, cycle 배열을 활용해서 음수 사이클 유무를 확인 할 수 있다.

시간 복잡도

최악의 경우 $O(|V| * |E|)$의 시간 복잡도를 가지지만, 실제로는 훨씬 빨리 돌아가는 알고리즘으로 $O(V + E)$ 혹은 $O(E)$라고 해도 무방하다고 합니다.

최선의 경우

최악의 경우

---

Reference

• Crocus - SPFA
• SPFA(Shortest Path Faster Algorithm) - Code Factory
• SPFA (Shortest Path Faster Algorithm)