新未名空间

foofy 写了： 2025年 5月 11日 02:03 https://mp.weixin.qq.com/s?__biz=MzAxMDg0OTUxNw==

近日，清华大学交叉信息院段然研究团队的论文“Breaking the Sorting Barrier for Directed Single-Source Shortest Paths”在理论计算机国际顶级会议STOC 2025（ACM SIGACT Symposium on Theory of Computing）上荣获最佳论文奖。

段然研究团队探讨了图论算法中经典的“单源最短路径问题（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级博士生毛啸。





论文原文：Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu, Longhui Yin (2025): „Breaking the Sorting Barrier for Directed Single-Source Shortest Paths“. 57th Annual ACM Symposium on Theory of Computing (STOC).

foofy 写了： 2025年 5月 11日 02:03 https://mp.weixin.qq.com/s?__biz=MzAxMDg0OTUxNw==

近日，清华大学交叉信息院段然研究团队的论文“Breaking the Sorting Barrier for Directed Single-Source Shortest Paths”在理论计算机国际顶级会议STOC 2025（ACM SIGACT Symposium on Theory of Computing）上荣获最佳论文奖。

段然研究团队探讨了图论算法中经典的“单源最短路径问题（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级博士生毛啸。





论文原文：Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu, Longhui Yin (2025): „Breaking the Sorting Barrier for Directed Single-Source Shortest Paths“. 57th Annual ACM Symposium on Theory of Computing (STOC).

foofy 写了： 2025年 5月 11日 02:03 https://mp.weixin.qq.com/s?__biz=MzAxMDg0OTUxNw==

近日，清华大学交叉信息院段然研究团队的论文“Breaking the Sorting Barrier for Directed Single-Source Shortest Paths”在理论计算机国际顶级会议STOC 2025（ACM SIGACT Symposium on Theory of Computing）上荣获最佳论文奖。

段然研究团队探讨了图论算法中经典的“单源最短路径问题（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级博士生毛啸。





论文原文：Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu, Longhui Yin (2025): „Breaking the Sorting Barrier for Directed Single-Source Shortest Paths“. 57th Annual ACM Symposium on Theory of Computing (STOC).

TestCases 写了： 2025年 5月 11日 03:39 有适用条件的。那就是稀疏图（SPARSE GRAPH). 这个算法不是一定就快，因为非稀疏图的话，M 可以接近O（N^2）.
大多数应用场景的抽象出来的图都是稀疏图（比如公路图），这个算法确实有可能很NB。

TestCases 写了： 2025年 5月 11日 03:39 有适用条件的。那就是稀疏图（SPARSE GRAPH). 这个算法不是一定就快，因为非稀疏图的话，M 可以接近O（N^2）.
大多数应用场景的抽象出来的图都是稀疏图（比如公路图），这个算法确实有可能很NB。

民主自由是婊子的遮羞布 写了： 2025年 5月 11日 03:48 大多数实际图是稀疏图

公路网、铁路网、航空hub网、路由器网、城市交通、物流配送网、机器人导航、资料中心网络拓朴

这些现实世界应用抽象出来的图几乎都是稀疏图

实际应用价值太高了，速度提高已经超越 log n 限制

foofy 写了： 2025年 5月 11日 02:03 https://mp.weixin.qq.com/s?__biz=MzAxMDg0OTUxNw==

近日，清华大学交叉信息院段然研究团队的论文“Breaking the Sorting Barrier for Directed Single-Source Shortest Paths”在理论计算机国际顶级会议STOC 2025（ACM SIGACT Symposium on Theory of Computing）上荣获最佳论文奖。

段然研究团队探讨了图论算法中经典的“单源最短路径问题（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级博士生毛啸。





论文原文：Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu, Longhui Yin (2025): „Breaking the Sorting Barrier for Directed Single-Source Shortest Paths“. 57th Annual ACM Symposium on Theory of Computing (STOC).

coltzhao 写了： 2025年 5月 11日 03:46 最主要的限制不是这个吧。
说的是经典Dijkstra 算法在过程中产生了源点到所有点距离的排序。
而这个新算法不会产生了源点到所有点距离的排序，也就是说是得到的是对单一或者一部分点的最短路径。

你要是求最短路径，这个计算应该是一定会小，除非你需要的是源点到所有点距离的排序。

民主自由是婊子的遮羞布 写了： 2025年 5月 11日 03:50 我大概算了一下

一万个节点的稀疏图，速度提高2倍以上

happens 写了： 2025年 5月 11日 03:50 一个新的图搜索算法？

民主自由是婊子的遮羞布 写了： 2025年 5月 11日 03:56 不是新算法，是改进

理论上有突破，但是实际应用意义更大

DonnieTrump 写了： 2025年 5月 11日 03:59 stoc不要求实验对比验证？

DonnieTrump 写了： 2025年 5月 11日 03:59 stoc不要求实验对比验证？

TestCases 写了： 2025年 5月 11日 03:54 我只看了摘要。在摘要里，他们的算法有个大O描述的算法效率，比之经典的Dijkstra的大O效率。好像窍门就是在这个用M取代N上，然后那个LOG_N部分，带了个（^(2/3))，这部分当然是变快了。所以我认为用M取代N，代价不能太大，那也就是他们自己也提到的，必须是稀疏图。
我没有看正文。

TestCases 写了： 2025年 5月 11日 03:54 我只看了摘要。在摘要里，他们的算法有个大O描述的算法效率，比之经典的Dijkstra的大O效率。好像窍门就是在这个用M取代N上，然后那个LOG_N部分，带了个（^(2/3))，这部分当然是变快了。所以我认为用M取代N，代价不能太大，那也就是他们自己也提到的，必须是稀疏图。
我没有看正文。