每次打開導(dǎo)航的，導(dǎo)航軟件在一秒內(nèi)給出一個最速路線的時候，你有沒有好奇過它是怎么找到這條路的？

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

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

Dijkstra 算法有多經(jīng)典呢？ 

可以說每一個學(xué)計算機的學(xué)生，甚至每一個學(xué)編程理論或數(shù)據(jù)結(jié)構(gòu)的人，都會在教科書上看到這個算法。

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

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

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

• 論文標(biāo)題：Breaking the Sorting Barrier for Directed Single-Source Shortest
• 論文鏈接：https://www.alphaxiv.org/abs/2504.17033

我們先一起回顧一下 Dijkstra 算法。這個最著名的最短路徑算法，由荷蘭計算機科學(xué)家艾茲赫爾?戴克斯特拉于 1956 年提出。 自此，它成為了計算機科學(xué)領(lǐng)域的經(jīng)典，廣泛應(yīng)用于網(wǎng)絡(luò)路由、地圖導(dǎo)航等各個領(lǐng)域。 Dijkstra 算法的目標(biāo)是找到從一個源點到圖中所有其他節(jié)點的最短路徑。它的基本思路是通過不斷選擇當(dāng)前最短的節(jié)點，并更新與之相鄰的節(jié)點的距離，直到所有節(jié)點的最短路徑都被找到。 

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

• 論文標(biāo)題： Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps
• 論文鏈接：https://arxiv.org/pdf/2311.11793

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

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

會后，毛嘯開始在空閑時間思考這一算法，而段然的團隊則在嘗試將已有的算法擴展到有向圖領(lǐng)域。受 Bellman-Ford 算法啟發(fā)，盡管這個算法比 Dijkstra 算法慢得多段然團隊通過將其分步執(zhí)行來避免慢速問題，并利用它提前發(fā)現(xiàn)關(guān)鍵節(jié)點。

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

他們是怎么做到的

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

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

對于無向圖，Pettie 和 Ramachandran（PR，2005）提出了一種基于層次結(jié)構(gòu)的算法，在比較 - 加法模型下可在  時間內(nèi)運行，其中 α 為反 Ackermann 函數(shù)，r 為任意兩條邊權(quán)之比的上界。

Dijkstra 算法還會在求解過程中額外生成按源點距離排序的頂點序列。最新研究表明，如果要求算法輸出按距離排序的頂點順序，那么 Dijkstra 算法是最優(yōu)的。若只需輸出頂點距離而不要求順序，段然、毛嘯團隊曾提出了一種適用于無向圖的隨機化 SSSP 算法，其時間復(fù)雜度為 ，在稀疏圖中優(yōu)于 O (n log n) 的結(jié)果。然而，對于有向圖，這類排序瓶頸依然沒有被突破。

定理 

存在一種確定性算法，可以在 時間內(nèi)求解具有實數(shù)非負邊權(quán)的有向圖單源最短路徑問題。

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

技術(shù)概述

總的來說，解決單源最短路徑問題有兩種傳統(tǒng)算法：

• Dijkstra 算法：通過優(yōu)先隊列，每次提取距離源點最近的頂點 u，并從該頂點松弛其所有出邊。該方法通常會根據(jù)頂點到源點的距離進行排序，因此時間復(fù)雜度至少為 Θ(n log n)。
• Bellman-Ford 算法：基于動態(tài)規(guī)劃思想，多次松弛所有邊。若要求解最多包含 k 條邊的最短路徑，Bellman-Ford 算法無需排序即可在 O (mk) 時間內(nèi)完成。

段然團隊的方法結(jié)合了這兩種思路，并采用遞歸劃分技術(shù)，這種技術(shù)類似于瓶頸路徑算法。

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

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

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

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

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

可以將前沿的大小 |S| 控制在 ，也就是「感興趣的頂點數(shù)」的 倍。

設(shè)參數(shù) ，有兩種情況：

1. 如果 |U?| > k?|S|，那么前沿大小已經(jīng)是 |U?| /k；

2. 否則，若 |U?| ≤ k?|S|，則從 S 中的頂點運行 Bellman-Ford 步驟 k 次，所有最短路徑中包含少于 k 個 U? 頂點的 u∈U? 都會被標(biāo)記為完成狀態(tài)。否則，若 u 所依賴的 S 中頂點 v 的最短路徑樹（SPT）中含有不少于 k 個 U? 頂點，那么可以將前沿 S 縮減為這些 “樞紐點（pivot）”，且這樣的樞紐點數(shù)量最多為 |U?| /k。

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

通過在每一層應(yīng)用前沿縮減策略，我們只需對這些樞紐點（約為前沿頂點的）執(zhí)行 Θ(t) 操作。這樣，每個頂點的處理時間就降低為 ，實現(xiàn)顯著加速。

算法

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

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

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

為了動態(tài)構(gòu)造這種結(jié)構(gòu)，他們每次嘗試計算一批最接近的頂點的距離（不必完全恢復(fù)它們的精確距離順序），并給出一個邊界值，表示實際推進了多少。

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

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

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

算法 1 查找關(guān)鍵樞紐點

算法 2 BMSSP 的基本情形

算法 3  有界多源最短路徑

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