清華新聞網(wǎng)5月13日電 近日，清華大學(xué)交叉信息院段然團(tuán)隊(duì)的論文“突破有向單源最短路徑的排序障礙”（Breaking the Sorting Barrier for Directed Single-Source Shortest Paths）在理論計(jì)算機(jī)國際頂級(jí)會(huì)議STOC 2025（ACM SIGACT Symposium on Theory of Computing,，ACM理論計(jì)算特別興趣小組理論計(jì)算研討會(huì)）上獲得最佳論文獎(jiǎng),。
段然團(tuán)隊(duì)探討了圖論算法中經(jīng)典的“單源最短路徑問題（SSSP）”。Dijkstra算法是解決這一問題的基本算法,，它以荷蘭計(jì)算機(jī)科學(xué)家埃德斯格爾·迪克斯特拉（Edsger Dijkstra）的名字命名,。自1956年開發(fā)以來，該算法一直被認(rèn)為是一項(xiàng)里程碑式的貢獻(xiàn),，被廣泛應(yīng)用于導(dǎo)航系統(tǒng)等,。為了改進(jìn)Dijkstra算法，該論文仔細(xì)研究了造成其大部分計(jì)算成本的部分：與所謂“優(yōu)先隊(duì)列 ”的交互,。在執(zhí)行過程中,，Dijkstra算法需要維護(hù)“前沿”，即已經(jīng)發(fā)現(xiàn)但尚未完全處理的頂點(diǎn)集合——這意味著它們與源點(diǎn)的暫定最短距離是已知的,，但算法可能尚未完全探索它們的鄰近頂點(diǎn),。這些前沿頂點(diǎn)存儲(chǔ)在一個(gè)優(yōu)先級(jí)隊(duì)列中，并從中反復(fù)提取下一個(gè)最近的頂點(diǎn),。Dijkstra算法中的前沿頂點(diǎn)可以多達(dá) “n”,，即頂點(diǎn)的數(shù)量。每次提取其中一個(gè)頂點(diǎn)的操作開銷為log（n）,，因此總時(shí)間為n log（n）,。研究團(tuán)隊(duì)提出的新算法通過融合Dijkstra算法和Bellman-Ford的教科書算法，以及一種巧妙設(shè)計(jì)的允許分組插入和提取的數(shù)據(jù)結(jié)構(gòu),，遞歸地縮小了所考慮的前沿的大小。因此,，操作的總數(shù)可以大大減少,，從而縮短了運(yùn)行時(shí)間，使整個(gè)算法運(yùn)行得更快,。
2024年圖靈獎(jiǎng)得主羅伯特·塔爾揚(yáng)（Robert Tarjan）及合作者發(fā)表的論文證明了Dijkstra算法對(duì)于“最短路徑排序問題”的普遍最優(yōu)性，獲得了FOCS 2024的最佳論文獎(jiǎng),，受到了《量子雜志》（Quanta Magazine）和量子位等媒體的報(bào)道,。單源最短路徑問題需要找到從一點(diǎn)s到其他所有點(diǎn)的最短路，而Dijkstra算法的副產(chǎn)品是所有點(diǎn)按照從源點(diǎn)的距離排序,，也就是說他們證明的是Dijkstra算法對(duì)于這個(gè)排序問題是普遍最優(yōu)的（universally optimal）,。但是段然團(tuán)隊(duì)的新算法避免了整體排序,，所以得到了比Dijkstra算法更快的最短路徑問題的算法。而且最短路徑問題明顯更加重要,，更快的最短路徑算法在理論上和實(shí)際應(yīng)用中都有很大意義。
清華大學(xué)交叉信息院副教授段然為論文通訊作者,，其他作者包括姚班2019屆本科畢業(yè)生束欣凱，以及姚班畢業(yè)生,、交叉信息院2022級(jí)博士生毛嘉怡和2021級(jí)博士生尹龍暉。斯坦福大學(xué)2022級(jí)博士生毛嘯也作出了貢獻(xiàn),。
供稿：交叉信息研究院
編輯：李華山
審核：郭玲
