【第503期】突破最短路径Dijkstra 算法的算法研究

Seventy3：借助NotebookLM的能力进行论文解读，专注人工智能、大模型、机器人算法、crypto方向，让大家跟着AI一起进步。

今天的主题是：

Breaking the Sorting Barrier for Directed Single-Source Shortest Paths

Summary

我们提出了一种确定性算法，在**比较–加法模型（comparison-addition model）下，用于求解带有实数非负边权的有向图单源最短路径（SSSP）**问题，其时间复杂度为O⁣(mlog⁡2/3n)。

这是首个在稀疏图上打破 Dijkstra 算法 O(m+nlog⁡n) 时间复杂度界限的结果，表明 Dijkstra 算法并非 SSSP 问题的最优算法。

原文链接：https://arxiv.org/abs/2504.17033