선형 시간 최단경로 알고리즘이라는데
이거 실제로 다익스트라보다 빠른가요?
다익스트라로는 안풀리고 이거써야 풀리는 문제 백준에 혹시 있음? 구현해보신분
논문보니까 이렇게 나오는데 진짜인지 궁금함
The time complexity for solving a single-source shortest path (SSSP) problem with Dijkstra's algorithm with a binary heap (DIJKSTRA-BH) is O((M+N)log N). An sophisticated algorithm called Thorup's algorithm has been proposed. The original version of Thorup's algorithm (THORUP-FR) has the time complexity of O(M+N). A simplified version of Thorup's algorithm (THORUP-KL) has the time complexity of O(Mα(N)+N) where α(N) is the functional inverse of the Ackerman function. In this paper, we compare the performances (i.e., execution time and memory consumption) of THORUP-KL and DIJKSTRA-BH since it is known that THORUP-FR is at least ten times slower than Dijkstra's algorithm with a Fibonaccii heap. We find that (1) THORUP-KL is almost always faster than DIJKSTRA-BH for large-scale network simulations, and (2) the performances of THORUP-KL and DIJKSTRA-BH deviate from their time complexities due to the presence of the memory cache in the microprocessor.
이거 실제로 다익스트라보다 빠른가요?
다익스트라로는 안풀리고 이거써야 풀리는 문제 백준에 혹시 있음? 구현해보신분
논문보니까 이렇게 나오는데 진짜인지 궁금함
The time complexity for solving a single-source shortest path (SSSP) problem with Dijkstra's algorithm with a binary heap (DIJKSTRA-BH) is O((M+N)log N). An sophisticated algorithm called Thorup's algorithm has been proposed. The original version of Thorup's algorithm (THORUP-FR) has the time complexity of O(M+N). A simplified version of Thorup's algorithm (THORUP-KL) has the time complexity of O(Mα(N)+N) where α(N) is the functional inverse of the Ackerman function. In this paper, we compare the performances (i.e., execution time and memory consumption) of THORUP-KL and DIJKSTRA-BH since it is known that THORUP-FR is at least ten times slower than Dijkstra's algorithm with a Fibonaccii heap. We find that (1) THORUP-KL is almost always faster than DIJKSTRA-BH for large-scale network simulations, and (2) the performances of THORUP-KL and DIJKSTRA-BH deviate from their time complexities due to the presence of the memory cache in the microprocessor.
NlogN 과 N은 차이가 클 듯 말 듯 해서 시간 책정이 어려워 그런 문제 만들기 되게 힘듦
입출력이 시간 다잡아먹어서 구별이 힘들겟네요 ...
이건 하계가 nlogn이 아니었나보네?
플로우도 O(N^(1.1)) 나왔는데 경로 쯤이야 더 작게 할 수도 있을 듯