清华新闻网5月13日电 近日，清华大学交叉信息院段然团队的论文“突破有向单源最短路径的排序障碍”（Breaking the Sorting Barrier for Directed Single-Source Shortest Paths）在理论计算机国际顶级会议STOC 2025（ACM SIGACT Symposium on Theory of Computing，ACM理论计算特别兴趣小组理论计算研讨会）上获得最佳论文奖。

段然团队探讨了图论算法中经典的“单源最短路径问题（SSSP）”。Dijkstra算法是解决这一问题的基本算法，它以荷兰计算机科学家埃德斯格尔·迪克斯特拉（Edsger Dijkstra）的名字命名。自1956年开发以来，该算法一直被认为是一项里程碑式的贡献，被广泛应用于导航系统等。为了改进Dijkstra算法，该论文仔细研究了造成其大部分计算成本的部分：与所谓“优先队列 ”的交互。在执行过程中，Dijkstra算法需要维护“前沿”，即已经发现但尚未完全处理的顶点集合——这意味着它们与源点的暂定最短距离是已知的，但算法可能尚未完全探索它们的邻近顶点。这些前沿顶点存储在一个优先级队列中，并从中反复提取下一个最近的顶点。Dijkstra算法中的前沿顶点可以多达 “n”，即顶点的数量。每次提取其中一个顶点的操作开销为log（n），因此总时间为n log（n）。研究团队提出的新算法通过融合Dijkstra算法和Bellman-Ford的教科书算法，以及一种巧妙设计的允许分组插入和提取的数据结构，递归地缩小了所考虑的前沿的大小。因此，操作的总数可以大大减少，从而缩短了运行时间，使整个算法运行得更快。

2024年图灵奖得主罗伯特·塔尔扬（Robert Tarjan）及合作者发表的论文证明了Dijkstra算法对于“最短路径排序问题”的普遍最优性，获得了FOCS 2024的最佳论文奖，受到了《量子杂志》（Quanta Magazine）和量子位等媒体的报道。单源最短路径问题需要找到从一点s到其他所有点的最短路，而Dijkstra算法的副产品是所有点按照从源点的距离排序，也就是说他们证明的是Dijkstra算法对于这个排序问题是普遍最优的（universally optimal）。但是段然团队的新算法避免了整体排序，所以得到了比Dijkstra算法更快的最短路径问题的算法。而且最短路径问题明显更加重要，更快的最短路径算法在理论上和实际应用中都有很大意义。

清华大学交叉信息院副教授段然为论文通讯作者，其他作者包括姚班2019届本科毕业生束欣凯，以及姚班毕业生、交叉信息院2022级博士生毛嘉怡和2021级博士生尹龙晖。斯坦福大学2022级博士生毛啸也作出了贡献。

供稿：交叉信息研究院

编辑：李华山

审核：郭玲