40年后，Dijkstra算法極限再被突破，清華段然團隊更快最短路徑算法摘STOC最佳論文

（來源：機器之心）

每次打開導航的，導航軟件在一秒內給出一個最速路線的時候，你有沒有好奇過它是怎麼找到這條路的？

假如不考慮堵車、紅綠燈等交通影響因素，僅找到一條最短最快的路線，那不論如何也逃不掉 Dijkstra 算法。

按照傳統的 Dijkstra 算法，你將在整段路程中停下多次，尋找每一段的最短路徑，然后再去更新下一段如何最短，直到走到目的地。在抉擇的過程中會面臨着不斷選擇「最短」路徑的情形，還需要通過對比排序來決策。

Dijkstra 算法有多經典呢？ 

可以説每一個學計算機的學生，甚至每一個學編程理論或數據結構的人，都會在教科書上看到這個算法。

其在計算機學生心中地位甚至不亞於物理學中的基本定律，想到路徑最短，必然想到 Dijkstra。

不過，現在有種方法能直接讓你跳過不必要的排序，只專注於最重要的點之間的最短距離，大大縮短了所需要的計算時間。這就是清華交叉信息研究院段然團隊一項重磅研究給出的全新解法。這項研究還在理論計算機國際頂級會議 STOC 2025 上獲得最佳論文獎。

該算法改進了圖靈獎得主 Robert Tarjan 等人在 1984 年提出的 O(m + nlogn)算法，后者將 Dijkstra 最短路徑算法逼近了理論極限，但並沒有完全消除排序的複雜度影響。

• 論文標題：Breaking the Sorting Barrier for Directed Single-Source Shortest

• 論文鏈接：https://www.alphaxiv.org/abs/2504.17033

我們先一起回顧一下 Dijkstra 算法。這個最著名的最短路徑算法，由荷蘭計算機科學家艾茲赫爾・戴克斯特拉於 1956 年提出。 自此，它成爲了計算機科學領域的經典，廣泛應用於網絡路由、地圖導航等各個領域。 Dijkstra 算法的目標是找到從一個源點到圖中所有其他節點的最短路徑。它的基本思路是通過不斷選擇當前最短的節點，並更新與之相鄰的節點的距離，直到所有節點的最短路徑都被找到。 

去年這個經典算法達到了前所未有的新高度。這篇 FOCS 2024 的最佳論文證明：若我們把任務定義為距離排序問題，在合適的堆結構下，Dijkstra 在排序意義上是普適最優的；也就是説，一旦強制輸出排序，就別指望整體複雜度再降了。

• 論文標題： Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps

• 論文鏈接：https://arxiv.org/pdf/2311.11793

本次 STOC 最佳論文與之形成互補：避免排序→突破運行時間。他們關注距離的計算，而不關心頂點的具體順序。它通過分層遞歸的方式，對圖中的節點進行分組處理，並且只對關鍵節點進行細緻的最短路徑計算。這樣的設計避免了傳統 Dijkstra 算法中每次都需要排序的步驟，從而大幅度降低了計算的複雜度。

這個想法早在 2023 年就已經有了雛形。毛嘯在加利福尼亞的一次會議上聽到了段然關於無向圖算法的演講，雙方因此展開了對話。毛嘯一直仰慕段然的工作，第一次與他面對面交流時激動不已。 

會后，毛嘯開始在空閒時間思考這一算法，而段然的團隊則在嘗試將已有的算法擴展到有向圖領域。受 Bellman-Ford 算法啓發，儘管這個算法比 Dijkstra 算法慢得多段然團隊通過將其分步執行來避免慢速問題，並利用它提前發現關鍵節點。

2024 年 3 月，毛嘯提出了一種無需隨機性的解決方案，隨后加入段然團隊。他們經過幾個月的合作，結合彼此的想法，並借用段然 2018 年提出的突破性技巧，最終設計出一種新算法。該算法通過分層方式，像 Dijkstra 一樣從源點擴展，但利用 Bellman-Ford 算法識別關鍵節點，避免了排序瓶頸，比 Dijkstra 更高效。

他們是怎麼做到的

在這項研究中，團隊給出了一種在具有實數非負邊權的有向圖上的單源最短路徑（SSSP）的確定性 O (mlog2/3⁡n) 時間算法，在比較加法模型中。這是首次打破 Dijkstra 算法在稀疏圖上的 O (m+nlog⁡n) 時間界限的結果，表明 Dijkstra 算法不是 SSSP 的最佳選擇。

經典的 Dijkstra 算法 Dij（59），結合 Fibonacci 堆 FT（87）或松弛堆 DGST（88）等高級數據結構，可以在 O (m + n log n) 時間內求解單源最短路徑（SSSP）問題。該算法在比較 - 加法模型（comparison-addition model）下工作，這種模型適用於實數權重的輸入，限制算法只能對邊權進行比較和加法運算，並且每個操作的耗時為單位時間。

對於無向圖，Pettie 和 Ramachandran（PR，2005）提出了一種基於層次結構的算法，在比較 - 加法模型下可在 

時間內運行，其中 α 為反 Ackermann 函數，r 為任意兩條邊權之比的上界。

Dijkstra 算法還會在求解過程中額外生成按源點距離排序的頂點序列。最新研究表明，如果要求算法輸出按距離排序的頂點順序，那麼 Dijkstra 算法是最優的。若只需輸出頂點距離而不要求順序，段然、毛嘯團隊曾提出了一種適用於無向圖的隨機化 SSSP 算法，其時間複雜度為 

，在稀疏圖中優於 O (n log n) 的結果。然而，對於有向圖，這類排序瓶頸依然沒有被突破。

定理 

存在一種確定性算法，可以在 

時間內求解具有實數非負邊權的有向圖單源最短路徑問題。

研究的結果也是第一個在無向圖情形下打破 O (m + n log n) 時間界的確定性算法。

技術概述

總的來説，解決單源最短路徑問題有兩種傳統算法：

• Dijkstra 算法：通過優先隊列，每次提取距離源點最近的頂點 u，並從該頂點松弛其所有出邊。該方法通常會根據頂點到源點的距離進行排序，因此時間複雜度至少為 Θ(n log n)。

• Bellman-Ford 算法：基於動態規劃思想，多次松弛所有邊。若要求解最多包含 k 條邊的最短路徑，Bellman-Ford 算法無需排序即可在 O (mk) 時間內完成。

段然團隊的方法結合了這兩種思路，並採用遞歸劃分技術，這種技術類似於瓶頸路徑算法。

在 Dijkstra 算法執行過程中的任意時刻，優先隊列（堆）都會維護一個前沿（frontier）集合 S，其中包含一些頂點。

如果某個頂點 u 是「未完成的」（即當前的距離估計 d̂[u] 仍大於真實距離 d (u)），那麼從源點 s 到 u 的最短路徑必須經過某個已完成的頂點 v∈S。在這種情況下，我們稱 u 依賴於 S 中的某個頂點 v。不過集合 S 中的頂點並不保證全部都是已完成的。

Dijkstra 算法會選擇 S 中距離源點最近的頂點（它必定是已完成的），然后松弛從該頂點出發的所有邊。

運行時間的瓶頸在於：有時前沿集合可能包含 Θ(n) 個頂點。由於需要不斷選出距離源點最近的頂點，這意味着必須維護這些頂點的全局有序性，因此無法突破 Ω(n log n) 的排序下界。

核心思想是縮小前沿集合的規模。假設我們只想計算距離小於某個上界 B 的所有頂點的最短路徑。令 Ũ  表示所有滿足 d (u) < B 且從 s 到 u 的最短路徑會經過集合 S 中某個頂點的頂點集合。

可以將前沿的大小 |S| 控制在 

倍。

，也就是「感興趣的頂點數」的

設參數 

，有兩種情況：

1. 如果 |Ũ| > k・|S|，那麼前沿大小已經是 |Ũ| /k；

2. 否則，若 |Ũ| ≤ k・|S|，則從 S 中的頂點運行 Bellman-Ford 步驟 k 次，所有最短路徑中包含少於 k 個 Ũ 頂點的 u∈Ũ 都會被標記為完成狀態。否則，若 u 所依賴的 S 中頂點 v 的最短路徑樹（SPT）中含有不少於 k 個 Ũ 頂點，那麼可以將前沿 S 縮減為這些 「樞紐點（pivot）」，且這樣的樞紐點數量最多為 |Ũ| /k。

算法基於以上思想，但與傳統 Dijkstra 類似的動態前沿方式不同，研究團隊採用分治（divide-and-conquer）方案：算法分為 log n /t 層，每層包含一組前沿頂點和一個上界 B。在朴素實現中，每個前沿頂點都需要花費 Θ(t) 時間處理，因此整體仍是每個頂點 Θ(log n) 的開銷。

通過在每一層應用前沿縮減策略，我們只需對這些樞紐點（約為前沿頂點的

執行 Θ(t) 操作。這樣，每個頂點的處理時間就降低為 

，實現顯著加速。

算法

該團隊研究的是常數度圖中從源點 s 出發的單源最短路徑問題，且 m = O (n)。在算法中，他們設兩個參數：

他們的核心思想是基於頂點集的分治。我們希望將一個頂點集 U 劃分爲 2^t 個大小相近的部分：

其中越靠前的子集中的頂點距離越小，然后遞歸地繼續劃分每個 U_i。這樣，經過大約 (log n) /t 層遞歸后，子問題規模將縮小到單個頂點。

爲了動態構造這種結構，他們每次嘗試計算一批最接近的頂點的距離（不必完全恢復它們的精確距離順序），並給出一個邊界值，表示實際推進了多少。

假設在算法的某個階段，對於所有 d (u) < b 的頂點 u，它們都已完成，並且團隊已經松弛了從它們出發的所有邊。此時他們想要找到所有 d (v) ≥ b 頂點的真實距離。

爲了避免優先隊列中每個頂點 Θ(log n) 的時間開銷，他們考慮一個前沿集 S，其中包含所有當前滿足 b ≤ d^(v) < B 的頂點（這里 B 是某個上界，並且不對它們進行排序）。可以發現，對於任意未完成頂點 v’ 且 b ≤ d (v’) < B，它的最短路徑一定會經過某個已完成的頂點 u ∈ S。

因此，要計算所有 b ≤ d (v’) < B 頂點的真實距離，只需找到從 S 中的頂點出發、距離受限於 B 的最短路徑。他們將這個子問題稱為有界多源最短路徑（Bounded Multi-Source Shortest Path，BMSSP），併爲其設計了一個高效算法。

更多引理及證明、算法細節以及觀察結論請參照原論文。

參考鏈接：

https://www.quantamagazine.org/new-method-is-the-fastest-way-to-find-the-best-routes-20250806/