spfa1 SPFA Optimization Techniques Shortest Path Faster Algorithm(SPFA) 알고리즘이 무엇인지 궁금하다면 이 게시글을 참고하자. 본 글에서는 SPFA 최적화 기법에 대해서만 서술하겠다. 1. Small Label First (SLF) 큐(Queue)에 최단 거리를 갱신할 수 있는 점(v)를 삽입할 때에, 큐의 가장 앞 부분에 위치한 정점(u)과 최단 거리를 비교한다. 만약 시작점으로부터 u에 이르는 거리보다 v에 이르는 거리가 더 짧다면, 큐의 가장 앞 부분에 v를 삽입하면 된다. 아래의 코드는 BOJ 1753번에 위 방법을 적용한 것이다. 2. Large Label Last (LLL) 큐(Queue)에 최단 거리를 갱신할 수 있는 점(v)를 삽입할 때에, 시작점으로부터 큐에 들어가 있는 정점들에 이르는 최단 거.. 2019. 10. 18. 이전 1 다음