English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

This paper proves that Dijkstra's shortest-path algorithm is universallyoptimal in both its running time and number of comparisons when combined with asufficiently efficient heap data structure.  Universal optimality is a powerful beyond-worst-case performance guaranteefor graph algorithms that informally states that a single algorithm performs aswell as possible for every single graph topology. We give the first applicationof this notion to any sequential algorithm.  We design a new heap data structure with a working-set property guaranteeingthat the heap takes advantage of locality in heap operations. Our heap matchesthe optimal (worst-case) bounds of Fibonacci heaps but also provides thebeyond-worst-case guarantee that the cost of extracting the minimum element ismerely logarithmic in the number of elements inserted after it instead oflogarithmic in the number of all elements in the heap. This makes theextraction of recently added elements cheaper.  We prove that our working-set property is sufficient to guarantee universaloptimality, specifically, for the problem of ordering vertices by theirdistance from the source vertex: The locality in the sequence of heapoperations generated by any run of Dijkstra's algorithm on a fixed topology isstrong enough that one can couple the number of comparisons performed by anyheap with our working-set property to the minimum number of comparisonsrequired to solve the distance ordering problem on this topology.

Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps