計算機科學的重大成果！

清華大學教授刷新最短路徑算法認知，或將改寫計算機算法教科書。

在計算機科學中，一個經典問題是尋找網絡中每個點的最短路徑，而Dijkstra算法是此問題的最經典解決方法。

自1956年來，最短路徑問題吸引了眾多研究人員的關注。

哥本哈根大學計算機科學家Mikkel Thorup米克爾·索魯普表示:

最短路徑是個絕妙的好問題，全世界人都能感同身受。

直覺上，找到離起點最近的點的路徑應該最簡單。

因此，如果想設計一個解決最短路徑問題的最快算法，合理的做法是先找到最近的點，然后是次近的點，依此類推。但這意味著你需要反復確定哪個點是最近的，也就是說，你得按距離給這些點排序。

然而，這種方法有一個根本的限制：這種算法的速度無法快過排序所需的時間。

四十年前，研究最短路徑算法的科學家們遇到了這個「排序瓶頸」。

現在，來自清華大學等機構的研究團隊設計了一種新算法，突破了這一瓶頸。這種算法不依賴排序，而且比任何需要排序的算法運行得更快。

論文鏈接：https://arxiv.org/abs/2504.17033

普林斯頓大學的計算機科學家Robert Tarjan說：「這些研究者大膽地認為他們能打破這個瓶頸。這是一個驚艷的成果。」

值得一提的是，這項研究摘得STOC最佳論文，實至名歸。

左：Mikkel Thorup；右：Robert Tarjan

最短路徑

若想解決復雜難題，條理分明往往事半功倍。比如將問題拆解后優先處理最簡單的部分——但這種分類需要代價，你可能耗費過多時間在排序上。

這一困境尤其體現在計算機科學中最經典的問題之一：如何在網絡中從特定起點出發，找到通往其他所有點的最短路徑。這就像日常搬家后必須解決的升級版問題：規劃從新家到公司、健身房和超市的最佳路線。

為了從數學角度分析最短路徑問題，研究者們使用圖論的語言——圖是由點（或稱節點）組成的網絡，這些點通過線連接起來。每條連接線都標有一個數字，叫作權重，它可以代表這段線的長度或穿越它所需的時間。

通常，任意兩個節點之間都有很多路徑，最短路徑就是那些權重加起來最小的路徑。給定一個圖和一個特定的「起點」，算法的目標就是找到到其他每個節點的最短路徑。

在1956年，計算機科學先驅埃茲赫·迪杰斯特拉（Edsger Dijkstra）設計了日后最著名的最短路徑算法。

它從起點開始，一步步向外擴展。

Dijkstra算法如何找到最短路徑

Dijkstra算法從網絡中的一個特定點開始，找到到每個其他點的最短路徑。它按距離從近到遠的順序找到這些路徑。

Dijkstra算法的基本步驟：

從A點開始：  

你看到兩條路徑。B點距離1單位，C點距離5單位。你現在知道到B的最短路徑，但可能有一條更短的間接路徑到C。 最短路徑：A → B = 1  

跟隨最短路徑：

前往 B，然后再觀察一次，記錄從 A 到每個點的總距離。D點比C點離 A 更近。最短路徑：A → B = 1；A → D = 2  

繼續探索:

前往D點并再次觀察，現在你已經找到了到C的最短路徑。最短路徑  ：A → B = 1；A → D = 2；A → C = 3。

從起點開始，逐步探索網絡中到每個點的最短路徑——這種方法很有效，因為知道到附近節點的最短路徑，能幫助你找到到更遠節點的最短路徑。

但最終結果是一個按距離排序的最短路徑列表，因此排序瓶頸設定了算法速度的根本限制。

1984年，Tarjan和另一位研究者改進了迪杰斯特拉的原始算法，使其達到了這個速度極限。任何進一步的改進都必須來自一個避免排序的算法。

論文鏈接：https://dl.acm.org/doi/10.1145/28869.28874

在20世紀90年代末和21世紀初，Thorup和其他研究者設計出了打破排序瓶頸的算法。

從左至右：Bernhard Haeupler、Václav Rozhoň（上方）、Jakub Tětek（下方）、Robert Tarjan和Richard Hladík證明了Dijkstra算法的一個版本是對所有網絡布局的最佳解決方案

他們需要對權重做出某些假設。沒人知道如何將這些技術擴展到任意權重上。似乎他們已經走到了盡頭。

研究停滯了很長一段時間，很多人相信沒有更好的辦法了。

但清華的段然不是其中之一。他長期夢想構建一個能在所有圖上突破排序瓶頸的最短路徑算法。去年秋天，他終于成功了。

超越排序

段然對排序瓶頸的關注可以追溯到近20年前。

那時，他在密歇根大學讀研究生。他的導師是研究如何在特定情況下打破排序瓶頸的學者之一。

但直到2021年，段然才找到一個更有前景的方法。

關鍵在于關注算法每一步的下一步走向。

迪杰斯特拉的算法會利用之前已探索的區域，決定下一步通過掃描這個區域的「邊界」——也就是所有與邊界相連的節點。起初這不會花太多時間，但隨著算法推進，速度會變慢。

段然則設想將邊界上的相鄰節點分組，形成多個集群。每一步只考慮每個集群中的一個節點。由于需要篩選的節點減少了，每一步的搜索都能更快。算法可能不會總是選擇最近的節點，因此排序瓶頸不再適用。但要確保這種基于集群的方法確實能加速算法，而不是讓它更慢，是一個挑戰。

在接下來的一年里，段然完善了這個基本想法。

到2022年秋天，他樂觀地認為自己能克服技術難題。

他拉來三位研究生幫忙細化細節，幾個月后，他們取得了部分成功——開發出了一種算法，打破了任意權重下的排序瓶頸，但僅適用于所謂無向圖。

論文鏈接：https://arxiv.org/abs/2307.04139

在無向圖中，每條連接線都可以雙向通行。計算機科學家通常更關注包含單向路徑的更廣義的圖類，但這些「有向圖」往往更難處理。

這次新論文的合著者、斯坦福大學計算機科學博士生毛嘯說：「（在有向圖中）可能存在一種情況，A到B很容易，但B到A卻很困難。這會給你帶來很多麻煩。」

希望之路

2023年夏天，在加州的一場學術會議上，毛嘯聆聽了段然關于無向圖算法的演講。他主動與這位仰慕已久的學者攀談起來。

那是他第一次在現實中見到段然，當時非常激動。

隨機性如何優化算法

會議結束后，毛嘯開始利用業余時間思考這個問題。與此同時，段和他的團隊正在探索適用于有向圖的新方法。他們從最短路徑問題的另一經典算法——貝爾曼-福特算法中汲取靈感。

貝爾曼-福特算法不生成排序列表，但初看卻像是個糟糕的選擇：它的速度遠遜于迪杰斯特拉算法。

計算機科學家米克爾·索魯普補充道：「科研就是不斷嘗試有潛力的路徑。但借鑒貝爾曼-福特算法簡直像在反其道而行——這看起來蠢透了。」

段然的團隊通過分階段運行貝爾曼-福特算法避開了其低速缺陷。這種選擇性使用讓他們能預先偵察后續步驟中最有價值的節點，這些節點如同交通網絡中的核心樞紐。

計算機科學家米克爾·索魯普解釋道：「要獲取多數目的地的最短路徑，你必須經過這些關鍵點」。

2024年3月，毛嘯提出另一創新思路。

原算法中某些關鍵步驟依賴隨機性，雖然隨機算法能高效解決許多問題，但學界仍更青睞確定性方案。

毛嘯設計出無需隨機化的最短路徑求解方法，隨后加入團隊。

通過數月的群聊和視頻會議，他們最終在秋季取得突破——段然教授意識到可借鑒其2018年解決另一類圖問題時突破排序障礙的技術，這正是補齊最后一塊拼圖的關鍵。

層進式革新

最終算法將圖分層處理，像迪杰斯特拉算法那樣從源頭向外推進。

但其精妙之處在于：通過貝爾曼-福特算法定位關鍵節點后優先探索，稍后回溯處理其他邊界節點。由于不嚴格按距離順序探索每層節點，排序障礙自然失效。若采用恰當的分層策略，其速度甚至略超優化版迪杰斯特拉算法。

這個由多個精密模塊組成的算法雖復雜，卻意外地未使用任何高深數學工具。

計算機科學家米克爾·索魯普感慨萬分：「這套方法本可能在五十年前就被發現，但直到現在才問世。這才更顯其非凡。」

段然團隊正著手優化算法以追求更快的速度。隨著排序障礙的攻克，新算法的運行效率已遠超現有理論極限。