2023/07/09 by Ran Duan, Duan, Ran, Jiayi Mao +5 · 5 citations
Computer Science · Biochemistry, Genetics and Molecular Biology · #Complexity and Algorithms in Graphs #Advanced biosensing and bioanalysis techniques #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.2307.04139
In undirected graphs with real non-negative weights, we give a new randomized algorithm for the single-source shortest path (SSSP) problem with running time O(m√(log n ⋅ loglog n)) in the comparison-addition model. This is the first algorithm to break the O(m+nlog n) time bound for real-weighted sparse graphs by Dijkstra's algorithm with Fibonacci heaps. Previous undirected non-negative SSSP algorithms give time bound of O(mα(m,n)+min\nlog n, nloglog r\) in comparison-addition model, where α is the inverse-Ackermann function and r is the ratio of the maximum-to-minimum edge weight [Pettie & Ramachandran 2005], and linear time for integer edge weights in RAM model [Thorup 1999]. Note that there is a proposed complexity lower bound of Ω(m+min\nlog n, nloglog r\) for hierarchy-based algorithms for undirected real-weighted SSSP [Pettie & Ramachandran 2005], but our algorithm does not obey the properties required for that lower bound. As a non-hierarchy-based approach, our algorithm shows great advantage with much simpler structure, and is much easier to implement.