알고리즘 공부방

SPFA 는 벨만 포드 알고리즘의 확장 알고리즘이다. 벨만 포드에서 1 단계의 완화를 시킬때, 간선들을 임의로 골라서 완화시켰기 때문에 비효율적인 면이 있었다. 어떠한 정점의 최단거리가 감소하지 않았다면, 그 정점에서 시작하는 간선들을 완화시키는 것은 의미가 없다. 이를 이용하면, 어떠한 정점이 완화되어 최단거리가 바뀌었다면, 그 정점으로부터 시작하는 간선들만 완화해주면 된다. 이는 BFS 와 비슷하게 큐를 이용하여 구현할 수 있다. 처음에 시작점을 큐에 넣어논 후, 그 정점으로부터 완화를 시키고, 또 성공적으로 완화된 정점들에 대해서 다시 큐에 넣어준다. 이 방법도 벨만포드와 마찬가지로 $O(VE)$ 이다. 하지만, 만약 어떤 정점 v가 이미 큐에 들어가 있고, 아직 큐에서 나오지 않은 상태인데, 지금..