Exploring Monotone Priority Queues for Dijkstra Optimization
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912074242719744 |
|---|---|
| author | Costa, Jonas Castro, Lucas de Freitas, Rosiane |
| author_facet | Costa, Jonas Castro, Lucas de Freitas, Rosiane |
| contents | This paper presents a comprehensive overview of monotone priority queues, focusing on their evolution and application in shortest path algorithms. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_06061 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Exploring Monotone Priority Queues for Dijkstra Optimization Costa, Jonas Castro, Lucas de Freitas, Rosiane Data Structures and Algorithms This paper presents a comprehensive overview of monotone priority queues, focusing on their evolution and application in shortest path algorithms. 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. |
| title | Exploring Monotone Priority Queues for Dijkstra Optimization |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2409.06061 |