近日，清華大學交叉信息院段然團隊的論文“突破有向單源最短路徑的排序障礙”（Breaking the Sorting Barrier for Directed Single-Source Shortest Paths）在理論計算機國際頂級會議STOC 2025（ACM SIGACT Symposium on Theory of Computing，ACM理論計算特別興趣小組理論計算研討會）上獲得最佳論文獎。

段然團隊探討了圖論算法中經(jīng)典的“單源最短路徑問題（SSSP）”。Dijkstra算法是解決這一問題的基本算法，它以荷蘭計算機科學家埃德斯格爾·迪克斯特拉（Edsger Dijkstra）的名字命名。自1956年開發(fā)以來，該算法一直被認為是一項里程碑式的貢獻，被廣泛應用于導航系統(tǒng)等。為了改進Dijkstra算法，該論文仔細研究了造成其大部分計算成本的部分：與所謂“優(yōu)先隊列 ”的交互。在執(zhí)行過程中，Dijkstra算法需要維護“前沿”，即已經(jīng)發(fā)現(xiàn)但尚未完全處理的頂點集合——這意味著它們與源點的暫定最短距離是已知的，但算法可能尚未完全探索它們的鄰近頂點。這些前沿頂點存儲在一個優(yōu)先級隊列中，并從中反復提取下一個最近的頂點。Dijkstra算法中的前沿頂點可以多達 “n”，即頂點的數(shù)量。每次提取其中一個頂點的操作開銷為log（n），因此總時間為n log（n）。研究團隊提出的新算法通過融合Dijkstra算法和Bellman-Ford的教科書算法，以及一種巧妙設計的允許分組插入和提取的數(shù)據(jù)結(jié)構(gòu)，遞歸地縮小了所考慮的前沿的大小。因此，操作的總數(shù)可以大大減少，從而縮短了運行時間，使整個算法運行得更快。

2024年圖靈獎得主羅伯特·塔爾揚（Robert Tarjan）及合作者發(fā)表的論文證明了Dijkstra算法對于“最短路徑排序問題”的普遍最優(yōu)性，獲得了FOCS 2024的最佳論文獎，受到了《量子雜志》（Quanta Magazine）和量子位等媒體的報道。單源最短路徑問題需要找到從一點s到其他所有點的最短路，而Dijkstra算法的副產(chǎn)品是所有點按照從源點的距離排序，也就是說他們證明的是Dijkstra算法對于這個排序問題是普遍最優(yōu)的（universally optimal）。但是段然團隊的新算法避免了整體排序，所以得到了比Dijkstra算法更快的最短路徑問題的算法。而且最短路徑問題明顯更加重要，更快的最短路徑算法在理論上和實際應用中都有很大意義。

清華大學交叉信息院副教授段然為論文通訊作者，其他作者包括姚班2019屆本科畢業(yè)生束欣凱，以及姚班畢業(yè)生、交叉信息院2022級博士生毛嘉怡和2021級博士生尹龍暉。斯坦福大學2022級博士生毛嘯也作出了貢獻。