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)를 삽입할 때에, 시작점으로부터 큐에 들어가 있는 정점들에 이르는 최단 거리값의 평균값을 X라고 하자. 시작 정점으로부터 큐의 가장 앞 부분에 위치한 정점 사이의 최단 거리가 항상 X보다 작게 유지하고, 만약 더 큰 정점이 있다면 큐의 가장 뒷 부분으로 보낸다.

아래의 코드는 BOJ 1753번에 위 방법을 적용한 것이다.