Faster single-source shortest paths with negative real weights via proper hop distance

2024/07/05 by Y. P. Huang, Huang, Yufan, Peter Jin +3 · 8 citations
Engineering · Computer Science · #Sparse and Compressive Sensing Techniques #Speech and Audio Processing #Blind Source Separation Techniques

paper · pdf · doi:10.48550/arxiv.2407.04872

Abstract

The textbook algorithm for single-source shortest paths with real-valued edge weights runs in O(m n) time on a graph with m edges and n vertices. A recent breakthrough algorithm by Fineman [Fin24] takes O(m n^8/9) randomized time. We present an O(m n^4/5) randomized time algorithm building on ideas from [Fin24].

Cited by

• From Hop Reduction to Sparsification for Negative Length Shortest Paths
• Shortcutting for Negative-Weight Shortest Path
• Deterministic Padded Decompositions and Negative-Weight Shortest Paths
• Faster Negative-Weight Shortest Paths and Directed Low-Diameter Decompositions
• Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP
• A Faster Directed Single-Source Shortest Path Algorithm
• A Refutation of Elmasry's O(m √(n))-Time Algorithm for Single-Source Shortest Paths
• Quantum Speedups for Polynomial-Time Dynamic Programming Algorithms

Related

• Faster negative length shortest paths by bootstrapping hop reducers
• Single-Source Shortest Paths with Negative Real Weights in O(mn^8/9) Time
• From Hop Reduction to Sparsification for Negative Length Shortest Paths
• Negative-Weight Single-Source Shortest Paths in Near-linear Time
• Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster!