Exploring monotone priority queues for Dijkstra optimization

This paper presents a comprehensive overview of monotone priority queues and their pivotal role in optimizing Dijkstra’s shortest path algorithm. Its significance lies in detailing how exploiting specific properties of the shortest path problem, particularly the non-decreasing nature of extracted keys and the assumption of non-negative integer edge weights, leads to highly efficient priority queue implementations. These specialized data structures often outperform general-purpose priority queues in this domain.

The central innovation explored is the concept of a monotone priority queue, defined as one where the minimum key extracted never decreases over time. This property is inherently met by label-setting algorithms like Dijkstra’s, making these tailored priority queues highly effective.

Key innovations discussed include:

1. Dial’s 1-Level Bucket Structure: This foundational innovation implicitly uses a monotone priority queue. It organizes elements into an array of “buckets,” where each bucket B[i] holds vertices whose current shortest path distance from the source is i. The algorithm simply extracts from the lowest-indexed non-empty bucket. This simple design, exploiting the integer nature and non-decreasing property of distances, provides a base complexity of O(m + nC), where m is the number of edges, n the number of vertices, and C is the maximum arc weight.

2. Multi-Level Bucket Structures: To improve upon Dial’s algorithm, specifically to reduce the cost of scanning many empty buckets during extract-min operations, multi-level structures were developed.

   • 2-Level Buckets (Denardo & Fox): This innovation introduced a hierarchy, typically with a top level of √C + 1 buckets, each containing √C + 1 bottom-level buckets. This reduces the search for the next minimum element from O(C) to O(√C), yielding a Dijkstra complexity of O(m + n√C).
   • k-Level Buckets: Generalizing the 2-level approach, this structure further reduces the dependence on C to O(C^(1/k)) for k levels, leading to complexities like O(km + n(k + C^(1/k))). Modern implementations often use bit manipulation and the RAM model to achieve even better theoretical bounds, sometimes reaching O(m + nC) for practical purposes by cleverly packing information.

3. Hot Queues (Cherkassky et al.): This innovation combines the benefits of bucket structures with a general-purpose heap (like a Fibonacci heap or Thorup’s heap). The idea is to direct elements to the heap if the active bucket in the multi-level structure contains few elements, thereby avoiding expensive “expansions” or reorganizations that occur when a small bucket needs to be distributed into a lower level. This hybrid approach aims for strong amortized theoretical bounds while maintaining practical efficiency.

4. Radix Heaps (Ahuja et al.): Distinct from simple bucket structures, radix heaps exploit the property that successive extracted minimum keys are non-decreasing. They employ buckets with exponentially increasing widths (e.g., powers of 2). This allows for efficient insertion and decrease-key operations by mapping keys to appropriate variable-width buckets. Two-level radix heaps further improved performance, bringing Dijkstra’s complexity to O(m + n log(C)/log log(C)). Integrating these with Fibonacci heaps further refined the search for non-empty inner buckets.

5. Theoretical Limits and RAM Model Optimizations (Thorup): Landmark work by Thorup demonstrated that with the assumption of the Random Access Machine (RAM) model and integer keys, Dijkstra’s algorithm can achieve nearly linear time. This involves sophisticated bit manipulation and insights into the equivalence between sorting and monotone priority queues, pushing the theoretical boundaries for these specialized data structures to O(m log log(n)) or even O(m + n log log(C)) under certain conditions.

The main prior ingredients that these innovations build upon are:

• Dijkstra’s Algorithm: The fundamental shortest path algorithm itself, which forms the problem context and the target for optimization.
• Basic Priority Queue Operations: The standard insert, delete, extract-min, and crucially, decrease-key operations, which are fundamental to Dijkstra’s label-setting process.
• Comparison-Based Priority Queues: Standard data structures like binary heaps (providing O(log n) per operation) and more advanced Fibonacci heaps (achieving O(1) amortized for insert/decrease-key and O(log n) amortized for extract-min), which served as baselines for performance comparison and were sometimes integrated into hybrid structures (like hot queues).
• Integer Edge Weights and Bounded Maximum Weight (C): A critical assumption for the efficiency of all bucket-based and radix-based priority queues. The ability to use key values directly as array indices or to divide the key range into a fixed number of buckets is contingent on keys being non-negative integers with a known maximum C.
• The RAM Model: This computational model, which assumes constant-time access to memory locations and basic arithmetic/bitwise operations, is essential for achieving the advanced theoretical bounds seen in radix heaps and Thorup’s work.
• Moore’s Algorithm: An early predecessor to Dial’s work, providing an initial framework for shortest path calculation that implicitly used some form of bucket organization.