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

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 \sqrt{\log n \cdot \log \log n})$ in the comparison-addition model. This is the first algorithm to break the $O(m+n \log n)$ time bound for real-weighted sparse graphs by Dijkstra’s algorithm with Fibonacci heaps. Previous undirected nonnegative 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 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 $\Omega(m+\min \{n \log n, n \log \log 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-hierarchybased approach, our algorithm shows great advantage with much simpler structure, and is much easier to implement.

Authors

• Ran Duan
• Jiayi Mao
• Xinkai Shu
• Longhui Yin

Keywords

• Computer science
• Random access memory
• Complexity theory
• Undirected
• Shortest Path
• Single Source Shortest Path
• Running Time
• Edge Weights
• Linear Time
• Dijkstra’s Algorithm
• Shortest Path Problem
• Real Weight
• Leisure
• High Probability
• Deterministic
• Random Variables
• Loss Of Generality
• Time Complexity
• Correction Algorithm
• Addition Operations
• Vertices
• Formal Proof
• Constant Degree
• Priority Queue
• Graph Algorithms
• Ordering Of The Vertices
• Geometric Distribution
• Linear-time Algorithm
• Subset Of Vertices
• Insertion Time
• randomized algorithm