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