本科经典的Dijkstra算法被清华段然团队超越。该算法用于解决最短路径问题，去年刚被图灵奖得主Tarjan团队证明具有普遍最优性，而如今清华团队的新算法运行速度超过任何Dijkstra及其改进算法，还彻底解决了困扰研究人员四十多年的“排序障碍”，其关键在于完全不进行排序。
研究人员提出了一种在比较加法模型下，针对具有实数非负边权的有向图的单源最短路径（SSSP）确定性算法，其时间复杂度为O(mlog2/3n)。
这是首次打破稀疏图上Dijkstra算法的时间界限的成果，表明Dijkstra算法并非求解SSSP的最优算法。
核心思想是融合Dijkstra算法与Bellman-Ford算法的优势，通过递归分区技术（类似瓶颈路径算法中使用的技术）解决有向图单源最短路径（SSSP）问题。
论文
