清华大学段然副教授等提出了一种新的确定性算法，用于解决有向图中的单源最短路径（SSSP）问题，突破了传统Dijkstra算法的时间复杂度限制。
论文：http://t.cn/A6sZKm6O
该算法能在拥有 n 个顶点和 m 条边的有向图中，处理非负实数权重 ，其运行时间为 O(m log^(2/3)n) 。该算法首次在稀疏图上，打破了经典的 Dijkstra 算法及其变体（如使用斐波那契堆）所保持的长达数十年的 O(m + n log n) 时间复杂度壁垒 。这证明了对于求解最短路径的“距离值”而言，Dijkstra 算法并非最优选择 ，从而解决了有向图领域一个长期存在的公开问题 。