Análise assintótica e empírica de filas de prioridade avançadas aplicadas ao Algoritmo de Dijkstra - Fernandes, Ana Carla; Castro, Lucas; Clementino, Thailsson; Freitas, Rosiane de (Anais do Encontro de Teoria da Computação (ETC); 2026: Anais do XI Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2026.22057, 2026)
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.