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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

In undirected graphs with real non-negative weights, we give a new randomizedalgorithm for the single-source shortest path (SSSP) problem with running time$O(m\sqrt{\log n \cdot \log\log n})$ in the comparison-addition model. This isthe first algorithm to break the $O(m+n\log n)$ time bound for real-weightedsparse graphs by Dijkstra's algorithm with Fibonacci heaps. Previous undirectednon-negative SSSP algorithms give time bound of $O(m\alpha(m,n)+\min\{n\log n,n\log\log r\})$ in comparison-addition model, where $\alpha$ is theinverse-Ackermann function and $r$ is the ratio of the maximum-to-minimum edgeweight [Pettie & Ramachandran 2005], and linear time for integer edge weightsin RAM model [Thorup 1999]. Note that there is a proposed complexity lowerbound of $\Omega(m+\min\{n\log n, n\log\log r\})$ for hierarchy-basedalgorithms for undirected real-weighted SSSP [Pettie & Ramachandran 2005], butour algorithm does not obey the properties required for that lower bound. As anon-hierarchy-based approach, our algorithm shows great advantage with muchsimpler structure, and is much easier to implement.

A Randomized Algorithm for Single-Source Shortest Path on Undirected Real-Weighted Graphs