Exploring monotone priority queues for Dijkstra optimization
Jonas Costa, Lucas Castro, Rosiane de Freitas · RAIRO - Operations Research · 2025
The Shortest Path Problem (SPP) is one of the most significant problems in combinatorial optimization. Beyond the vast number of direct applications, the SPP frequently serves as a subroutine in solving other optimization problems. This paper presents a comprehensive review of monotone priority queues, a class of data structures that play a crucial role in solving the SPP efficiently. Monotone priority queues are characterized by the property that their minimum key does not decrease over time, making them particularly effective for label-setting algorithms like Dijkstra’s. Some key data structures within this category are explored, emphasizing those derived directly from Dial’s algorithm, including variations of multi-level bucket structures and radix heaps. Theoretical complexities and practical considerations of these structures are discussed, with insights into their development and refinement provided through a historical timeline.