Shortest Path Faster Algorithm (1) 썸네일형 리스트형 Shortest Path Faster Algorithm(SPFA) 이 게시글에서는 벨만 포드 알고리즘의 평균 시간 복잡도를 크게 개선한 SPFA의 구현법과 특징을 알아본다. SPFA의 사용 의의 SPFA의 시간 복잡도는 벨만 포드와 동일하게 $O(VE)$이지만 SPFA 저격 데이터가 없는 경우 $O(V + E)$의 성능을 낸다고 알려져 있다. 따라서 채점 데이터가 약하다고 추정되는 문제에서 최단 경로를 찾을 때는 SPFA의 사용을 고려할 수 있다. 단, 저격 데이터가 있는 경우 SPFA의 큐 사용에서 발생하는 상수 시간이 더 크기 때문에 벨만 포드보다 느린 퍼포먼스를 보여준다는 것을 유의해야 한다. SPFA는 MCMF의 구현에 많이 이용하므로 플로우와 관련된 알고리즘을 배우기 전에 꼭 숙지해야 하는 알고리즘이다. C++ 구현 SPFA는 큐를 이용해서 BFS와 유사하게 .. 이전 1 다음
