Avaliação do desempenho de Multilevel Bucket Queues na determinação de caminhos mínimos em arquiteturas modernas
Resumo
Filas compartimentadas (buckets) multinível exploram restrições de pesos inteiros para superar filas de prioridades de propósito geral no Algoritmo de Dijkstra. Entretanto, as razões em nível de hardware para essa vantagem ainda são pouco compreendidas. Neste trabalho são comparadas as filas de buckets de 1 a 6 níveis com heaps binário e de Fibonacci, em doze instâncias de redes viárias do Benchmark DIMACS. A variante de 1 nível com operação decrease-key alcança até 2× de aceleração em relação ao heap binário e 3,2× em relação ao heap de Fibonacci, o que se explica por um menor número de instruções de desvio (branch instructions) e por uma melhor utilização do cache. Para pesos máximos elevados (C ≥ 106), variantes com menos níveis apresentam degradação devido à manipulação da memória, sendo a variante de 5 níveis a que se observou oferecer melhor escalabilidade.
Referências
Brodal, G. S. (2013). A Survey on Priority Queues, pages 150–163. Springer Berlin Heidelberg, Berlin, Heidelberg.
Castro, L., Clementino, T., and de Freitas, R. (2025). Implementation and brief experimental analysis of the Duan et al. (2025) algorithm for single-source shortest paths.
Chen, M., Chowdhury, R. A., Ramachandran, V., Roche, D. L., and Tong, L. (2007). Priority queues and dijkstra’s algorithm. Technical report, Computer Science Department, University of Texas at Austin Austin, TX, USA.
Cherkassky, B. V., Goldberg, A. V., and Radzik, T. (1996). Shortest paths algorithms: Theory and experimental evaluation. Mathematical programming, 73(2):129–174.
Cherkassky, B. V., Goldberg, A. V., and Silverstein, C. (1997). Buckets, heaps, lists, and monotone priority queues. Association for Computing Machinery, New York, NY (United States).
Costa, Jonas, Castro, Lucas, and de Freitas, Rosiane (2025). Exploring monotone priority queues for dijkstra optimization. RAIRO-Oper. Res., 59(5):2419–2436.
cppreference.com (2024). std::priority queue. Acesso em: 30 mar. 2026.
Demetrescu, C., Goldberg, A. V., and Johnson, D. S., editors (2006). 9th DIMACS Implementation Challenge: Shortest Paths. American Mathematical Society.
Demetrescu, C., Goldberg, A. V., and Johnson, D. S. (2009). The shortest path problem: Ninth dimacs implementation challenge. In DIMACS Series in Discrete Mathematics and Theoretical Computer Science, volume 74. AMS.
Dial, R. B. (1969). Algorithm 360: shortest-path forest with topological ordering [h]. Commun. ACM, 12(11):632–633.
Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numer. Math., 1(1):269–271.
Duan, R., Mao, J., Mao, X., Shu, X., and Yin, L. (2025). Breaking the sorting barrier for directed single-source shortest paths. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC ’25, page 36–44, New York, NY, USA. Association for Computing Machinery.
Fredman, M. L. and Tarjan, R. E. (1987). Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM, 34(3):596–615.
Goldberg, A. V. and Silverstein, C. (1997). Implementations of dijkstra’s algorithm based on multi-level buckets. In Pardalos, P. M., Hearn, D. W., and Hager, W. W., editors, Network Optimization, pages 292–327, Berlin, Heidelberg. Springer Berlin Heidelberg.
Knuth, D. E. (1998). The Art of Computer Programming, volume 3. Addison-Wesley, Reading, Massachusetts, 2 edition.
Larkin, D. H., Sen, S., and Tarjan, R. E. (2014). A back-to-basics empirical study of priority queues. In Proceedings of the Meeting on Algorithm Engineering & Expermiments, page 61–72, USA. Society for Industrial and Applied Mathematics.
Lisitsyn, S., Widmer, C., and Garcia, F. J. I. (2013). Tapkee: An efficient dimension reduction library. Journal of Machine Learning Research, 14(36):2355–2359.
Madkour, A., Aref, W., Rehman, F., Rahman, A., and Basalamah, S. (2017). A survey of shortest-path algorithms.
Mrena, M., Sedlacek, P., and Kvassay, M. (2019). Practical applicability of advanced implementations of priority queues in finding shortest paths. In 2019 International Conference on Information and Digital Technologies (IDT), pages 335–344.
Otte, M. W. (2016). On solving floating point SSSP using an integer priority queue. CoRR, abs/1606.00726.
Roche, D. L. (2007). Experimental study of high performance priority queues. University of Texas Computer Sciences Undergraduate Thesis.
Thorup, M. (2000). On ram priority queues. SIAM Journal on Computing, 30(1):86–109.
Williams, J. (1964). Algorithm 232: Heapsort. Communications of the ACM, 7:347 – 348.
Castro, L., Clementino, T., and de Freitas, R. (2025). Implementation and brief experimental analysis of the Duan et al. (2025) algorithm for single-source shortest paths.
Chen, M., Chowdhury, R. A., Ramachandran, V., Roche, D. L., and Tong, L. (2007). Priority queues and dijkstra’s algorithm. Technical report, Computer Science Department, University of Texas at Austin Austin, TX, USA.
Cherkassky, B. V., Goldberg, A. V., and Radzik, T. (1996). Shortest paths algorithms: Theory and experimental evaluation. Mathematical programming, 73(2):129–174.
Cherkassky, B. V., Goldberg, A. V., and Silverstein, C. (1997). Buckets, heaps, lists, and monotone priority queues. Association for Computing Machinery, New York, NY (United States).
Costa, Jonas, Castro, Lucas, and de Freitas, Rosiane (2025). Exploring monotone priority queues for dijkstra optimization. RAIRO-Oper. Res., 59(5):2419–2436.
cppreference.com (2024). std::priority queue. Acesso em: 30 mar. 2026.
Demetrescu, C., Goldberg, A. V., and Johnson, D. S., editors (2006). 9th DIMACS Implementation Challenge: Shortest Paths. American Mathematical Society.
Demetrescu, C., Goldberg, A. V., and Johnson, D. S. (2009). The shortest path problem: Ninth dimacs implementation challenge. In DIMACS Series in Discrete Mathematics and Theoretical Computer Science, volume 74. AMS.
Dial, R. B. (1969). Algorithm 360: shortest-path forest with topological ordering [h]. Commun. ACM, 12(11):632–633.
Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numer. Math., 1(1):269–271.
Duan, R., Mao, J., Mao, X., Shu, X., and Yin, L. (2025). Breaking the sorting barrier for directed single-source shortest paths. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC ’25, page 36–44, New York, NY, USA. Association for Computing Machinery.
Fredman, M. L. and Tarjan, R. E. (1987). Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM, 34(3):596–615.
Goldberg, A. V. and Silverstein, C. (1997). Implementations of dijkstra’s algorithm based on multi-level buckets. In Pardalos, P. M., Hearn, D. W., and Hager, W. W., editors, Network Optimization, pages 292–327, Berlin, Heidelberg. Springer Berlin Heidelberg.
Knuth, D. E. (1998). The Art of Computer Programming, volume 3. Addison-Wesley, Reading, Massachusetts, 2 edition.
Larkin, D. H., Sen, S., and Tarjan, R. E. (2014). A back-to-basics empirical study of priority queues. In Proceedings of the Meeting on Algorithm Engineering & Expermiments, page 61–72, USA. Society for Industrial and Applied Mathematics.
Lisitsyn, S., Widmer, C., and Garcia, F. J. I. (2013). Tapkee: An efficient dimension reduction library. Journal of Machine Learning Research, 14(36):2355–2359.
Madkour, A., Aref, W., Rehman, F., Rahman, A., and Basalamah, S. (2017). A survey of shortest-path algorithms.
Mrena, M., Sedlacek, P., and Kvassay, M. (2019). Practical applicability of advanced implementations of priority queues in finding shortest paths. In 2019 International Conference on Information and Digital Technologies (IDT), pages 335–344.
Otte, M. W. (2016). On solving floating point SSSP using an integer priority queue. CoRR, abs/1606.00726.
Roche, D. L. (2007). Experimental study of high performance priority queues. University of Texas Computer Sciences Undergraduate Thesis.
Thorup, M. (2000). On ram priority queues. SIAM Journal on Computing, 30(1):86–109.
Williams, J. (1964). Algorithm 232: Heapsort. Communications of the ACM, 7:347 – 348.
Publicado
19/07/2026
Como Citar
FERNANDES, Ana Carla; MIRANDA, Ricardo; FREITAS, Rosiane de.
Avaliação do desempenho de Multilevel Bucket Queues na determinação de caminhos mínimos em arquiteturas modernas. In: WORKSHOP EM DESEMPENHO DE SISTEMAS COMPUTACIONAIS E DE COMUNICAÇÃO (WPERFORMANCE), 25. , 2026, Gramado/RS.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2026
.
p. 117-128.
ISSN 2595-6167.
DOI: https://doi.org/10.5753/wperformance.2026.23674.
