https://arxiv.org/abs/2311.11793

close this message
arXiv Smilely Bones

Happy Open Access Week from arXiv!

Open access is only possible with YOUR support. Give to arXiv this
week to help keep science open for all.

Donate!
Skip to main content
Cornell University
We gratefully acknowledge support from the Simons Foundation, member
institutions, and all contributors. Donate
 
arxiv logo > cs > arXiv:2311.11793
[                    ]

Help | Advanced Search

[All fields        ]
Search
arXiv logo
Cornell University Logo
[                    ] GO
quick links

  * Login
  * Help Pages
  * About

Computer Science > Data Structures and Algorithms

arXiv:2311.11793 (cs)
[Submitted on 20 Nov 2023 (v1), last revised 9 Apr 2024 (this
version, v2)]

Title:Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps

Authors:Bernhard Haeupler, Richard Hladik, Vaclav Rozhon, Robert
Tarjan, Jakub Tetek
View a PDF of the paper titled Universal Optimality of Dijkstra via
Beyond-Worst-Case Heaps, by Bernhard Haeupler and 4 other authors
View PDF HTML (experimental)

    Abstract:This paper proves that Dijkstra's shortest-path
    algorithm is universally optimal in both its running time and
    number of comparisons when combined with a sufficiently efficient
    heap data structure.
    Universal optimality is a powerful beyond-worst-case performance
    guarantee for graph algorithms that informally states that a
    single algorithm performs as well as possible for every single
    graph topology. We give the first application of this notion to
    any sequential algorithm.
    We design a new heap data structure with a working-set property
    guaranteeing that the heap takes advantage of locality in heap
    operations. Our heap matches the optimal (worst-case) bounds of
    Fibonacci heaps but also provides the beyond-worst-case guarantee
    that the cost of extracting the minimum element is merely
    logarithmic in the number of elements inserted after it instead
    of logarithmic in the number of all elements in the heap. This
    makes the extraction of recently added elements cheaper.
    We prove that our working-set property is sufficient to guarantee
    universal optimality, specifically, for the problem of ordering
    vertices by their distance from the source vertex: The locality
    in the sequence of heap operations generated by any run of
    Dijkstra's algorithm on a fixed topology is strong enough that
    one can couple the number of comparisons performed by any heap
    with our working-set property to the minimum number of
    comparisons required to solve the distance ordering problem on
    this topology.

Subjects:    Data Structures and Algorithms (cs.DS)
ACM classes: F.2.2; G.2.2
Cite as:     arXiv:2311.11793 [cs.DS]
             (or arXiv:2311.11793v2 [cs.DS] for this version)
             https://doi.org/10.48550/arXiv.2311.11793
             Focus to learn more
             arXiv-issued DOI via DataCite

Submission history

From: Richard Hladik [view email]
[v1] Mon, 20 Nov 2023 14:21:47 UTC (338 KB)
[v2] Tue, 9 Apr 2024 23:33:15 UTC (340 KB)
Full-text links:

Access Paper:

    View a PDF of the paper titled Universal Optimality of Dijkstra
    via Beyond-Worst-Case Heaps, by Bernhard Haeupler and 4 other
    authors
  * View PDF
  * HTML (experimental)
  * TeX Source
  * Other Formats

view license
Current browse context:
cs.DS
< prev   |   next >
new | recent | 2023-11
Change to browse by:
cs

References & Citations

  * NASA ADS
  * Google Scholar
  * Semantic Scholar

1 blog link

(what is this?)
a export BibTeX citation Loading...

BibTeX formatted citation

x
[loading...          ]
Data provided by:

Bookmark

BibSonomy logo Reddit logo
(*) Bibliographic Tools

Bibliographic and Citation Tools

[ ] Bibliographic Explorer Toggle
Bibliographic Explorer (What is the Explorer?)
[ ] Litmaps Toggle
Litmaps (What is Litmaps?)
[ ] scite.ai Toggle
scite Smart Citations (What are Smart Citations?)
( ) Code, Data, Media

Code, Data and Media Associated with this Article

[ ] alphaXiv Toggle
alphaXiv (What is alphaXiv?)
[ ] Links to Code Toggle
CatalyzeX Code Finder for Papers (What is CatalyzeX?)
[ ] DagsHub Toggle
DagsHub (What is DagsHub?)
[ ] GotitPub Toggle
Gotit.pub (What is GotitPub?)
[ ] Huggingface Toggle
Hugging Face (What is Huggingface?)
[ ] Links to Code Toggle
Papers with Code (What is Papers with Code?)
[ ] ScienceCast Toggle
ScienceCast (What is ScienceCast?)
( ) Demos

Demos

[ ] Replicate Toggle
Replicate (What is Replicate?)
[ ] Spaces Toggle
Hugging Face Spaces (What is Spaces?)
[ ] Spaces Toggle
TXYZ.AI (What is TXYZ.AI?)
( ) Related Papers

Recommenders and Search Tools

[ ] Link to Influence Flower
Influence Flower (What are Influence Flowers?)
[ ] Connected Papers Toggle
Connected Papers (What is Connected Papers?)
[ ] Core recommender toggle
CORE Recommender (What is CORE?)

  * Author
  * Venue
  * Institution
  * Topic

( ) About arXivLabs

arXivLabs: experimental projects with community collaborators

arXivLabs is a framework that allows collaborators to develop and
share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have
embraced and accepted our values of openness, community, excellence,
and user data privacy. arXiv is committed to these values and only
works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community?
Learn more about arXivLabs.

Which authors of this paper are endorsers? | Disable MathJax (What is
MathJax?)

  * About
  * Help

  * Click here to contact arXiv Contact
  * Click here to subscribe Subscribe

  * Copyright
  * Privacy Policy

  * Web Accessibility Assistance
  * arXiv Operational Status
    Get status notifications via email or slack