Shortest Path Faster Algorithm(SPFA)

방향성 가중치 그래프 G = (V, E)에서 단일 시작점 s가 있을 때, Shortest Path Faster Algorithm(SPFA)는 s에서 출발하여 다른 정점 v에 이르는 최단경로를 찾아낸다. Pseudo Code를 보면 다음과 같다.

초기에 다른 정점에 이르는 최단거리는 다 무한대로 설정하고 시작점에 이르는 최단거리는 0으로 정한다.
Queue에 시작점을 넣고 Queue가 비어있지 않을 동안 반복한다.
Queue의 맨 앞에서 원소 하나를 꺼내서 그 정점을 u라고 하자.
u에서 뻗어나가는 간선들을 훑어보며, 간선이 가리키는 점 v의 최단거리를 갱신할 수 있으면 갱신해준다.
갱신하고 나서, Queue에 v가 없다면 Queue에 삽입한다.
Queue에 어떤 정점 x가 있는지, 없는지의 여부는 정점 크기의 1차원 배열을 하나 만듦으로써 O(1)에 판단하고 갱신할 수 있다.

SPFA의 평균적인 시간복잡도는 O(E)이지만, 최악에는 O(VE)이다.
각 정점에 이르는 최단경로의 길이를 담는 배열이 갱신되는 횟수를 통해 음수 사이클 여부도 판단할 수 있다.

예시로 BOJ 1753 최단경로 문제를 위의 SPFA로 구현해보았다.

맞은 사람 1248명 중 수행속도를 기준으로 보면 공동 7등이다.
코드의 길이 또한 매우 짧음을 알 수 있다.