Análise assintótica e empírica de filas de prioridade avançadas aplicadas ao Algoritmo de Dijkstra
Resumo
O problema do caminho mínimo é fundamental em diversas aplicações computacionais. Apesar dos recentes avanços teóricos, o Algoritmo de Dijkstra otimizado com filas de prioridade permanece como a solução de melhor desempenho prático. Este trabalho compara teórica e empiricamente heaps e bucket queues, explorando otimizações resultantes da monotonicidade e da restrição dos pesos dos grafos. Os resultados atestam o potencial das bucket queues multinível em grafos esparsos com pesos inteiros.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.
Costa, Jonas, Castro, Lucas, and de Freitas, Rosiane (2025). Exploring monotone priority queues for dijkstra optimization. RAIRO-Oper. Res., 59(5):2419–2436.
Demetrescu, C., Goldberg, A. V., and Johnson, D. S., editors (2006). 9th DIMACS Implementation Challenge: Shortest Paths. American Mathematical Society.
Denardo, E. V. and Fox, B. L. (1979). Shortest-route methods: 1. reaching, pruning, and buckets. Operations Research, 27(1):161–186.
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.
Grujic, Z. and Grujic, B. (2025). Optimal routing in urban road networks: A graph-based approach using dijkstra’s algorithm. Applied Sciences, 15(8).
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.
Tenenbaum, J. B., de Silva, V., and Langford, J. C. (2000). A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500):2319–2323.
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.
Costa, Jonas, Castro, Lucas, and de Freitas, Rosiane (2025). Exploring monotone priority queues for dijkstra optimization. RAIRO-Oper. Res., 59(5):2419–2436.
Demetrescu, C., Goldberg, A. V., and Johnson, D. S., editors (2006). 9th DIMACS Implementation Challenge: Shortest Paths. American Mathematical Society.
Denardo, E. V. and Fox, B. L. (1979). Shortest-route methods: 1. reaching, pruning, and buckets. Operations Research, 27(1):161–186.
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.
Grujic, Z. and Grujic, B. (2025). Optimal routing in urban road networks: A graph-based approach using dijkstra’s algorithm. Applied Sciences, 15(8).
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.
Tenenbaum, J. B., de Silva, V., and Langford, J. C. (2000). A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500):2319–2323.
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; CASTRO, Lucas; CLEMENTINO, Thailsson; FREITAS, Rosiane de.
Análise assintótica e empírica de filas de prioridade avançadas aplicadas ao Algoritmo de Dijkstra. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 11. , 2026, Gramado/RS.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2026
.
p. 41-45.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2026.22057.
