HyperAIHyperAI

Command Palette

Search for a command to run...

打破有向单源最短路径的排序障碍

Ran Duan Jiayi Mao Xiao Mao Xinkai Shu Longhui Yin

Abstract

我们提出了一种确定性算法,可在比较-加法模型下以 O(mlog2/3n)O(m \log^{2/3} n)O(mlog2/3n) 的时间复杂度解决具有非负实数边权的有向图上的单源最短路径(SSSP)问题。这是首个在稀疏图上突破 Dijkstra 算法 O(m+nlogn)O(m + n \log n)O(m+nlogn) 时间复杂度的成果,表明 Dijkstra 算法并非 SSSP 问题的最优解。


Build AI with AI

From idea to launch — accelerate your AI development with free AI co-coding, out-of-the-box environment and best price of GPUs.

AI Co-coding
Ready-to-use GPUs
Best Pricing

HyperAI Newsletters

订阅我们的最新资讯
我们会在北京时间 每周一的上午九点 向您的邮箱投递本周内的最新更新
邮件发送服务由 MailChimp 提供