Exploring monotone priority queues for Dijkstra optimization

DOI10.1051/RO/2025082MaRDI QIDQ6919281zbMATH OpenFDO

Authors Lucas Castro, Rosiane de Freitas

Publication date 8 October 2025

Published in RAIRO. Operations Research (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1051/RO/2025082

zbMATH Keywords

data structuresgraph algorithmspriority queuesshortest path problem

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Cites work

• A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees
• A note on two problems in connexion with graphs
• A Practical Shortest Path Algorithm with Linear Expected Time
• A Shortest Path Algorithm for Edge-Sparse Graphs
• A survey on priority queues
• Buckets, Heaps, Lists, and Monotone Priority Queues
• Comparaison d'algorithmes de plus courts chemins sur des graphes routiers de grande taille
• Design and implementation of an efficient priority queue
• Equivalence between priority queues and sorting
• Faster algorithms for the shortest path problem
• Fibonacci heaps and their uses in improved network optimization algorithms
• scientific article; zbMATH DE number 1086916 (Why is no real title available?)
• scientific article; zbMATH DE number 2081016 (Why is no real title available?)
• scientific article; zbMATH DE number 1875419 (Why is no real title available?)
• scientific article; zbMATH DE number 871900 (Why is no real title available?)
• scientific article; zbMATH DE number 7646025 (Why is no real title available?)
• Integer priority queues with decrease key in constant time and the single source shortest paths problem
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Preserving order in a forest in less than logarithmic time and linear space
• Priority queues: small, monotone and trans-dichotomous
• Shortest-Route Methods: 1. Reaching, Pruning, and Buckets
• Surpassing the information theoretic bound with fusion trees
• Undirected single-source shortest paths with positive integer weights in linear time

This page was built for publication: Exploring monotone priority queues for Dijkstra optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6919281)