Command Palette
Search for a command to run...
打破有向单源最短路径的排序障碍
打破有向单源最短路径的排序障碍
Ran Duan Jiayi Mao Xiao Mao Xinkai Shu Longhui Yin
Abstract
我们提出了一种确定性算法,可在比较-加法模型下以 O(mlog2/3n) 的时间复杂度解决具有非负实数边权的有向图上的单源最短路径(SSSP)问题。这是首个在稀疏图上突破 Dijkstra 算法 O(m+nlogn) 时间复杂度的成果,表明 Dijkstra 算法并非 SSSP 问题的最优解。