本科經典算法Dijkstra，被證明是普遍最優了：最壞情況性能也最優！

金磊 發自 凹非寺

量子位 | 公眾號 QbitAI

時隔近70年，那個用來解決最短路徑問題的經典算法——Dijkstra，現在有了新突破：

被證明具有普遍最優性（Universal Optimality）。

什麼意思？

這就意味著不論它面對多複雜的圖結構，即便在最壞情況下都能達到理論上的最優性能！

而且這還是學術界首次將這一概念應用於任何序列算法。

對於Dijkstra算法，想必很多人肯定不會陌生，畢竟它是每個計算機本科生必學的內容。

而且從它誕生至今，已經在廣泛地應用於我們的日常生活中，例如在Google地圖、蘋果地圖，Dijkstra算法就被用來計算從用戶當前位置到目的地的最優路線。

在計算機網絡中，被廣泛應用於路由協議中；例如開放最短路徑優先（OSPF）協議就是基於Dijkstra算法來計算網絡中數據包的最優傳輸路徑。

再如通信網絡設計、機器人路徑規劃和物流運輸優化等領域，也是處處都有它的身影。

（相關教程可參考：https://www.youtube.com/watch?v=EFg3u_E6eHU）

而這項集結了蘇黎世聯邦理工、CMU、普林斯頓等頂尖高校科研人員之力的研究，一舉讓這個經典算法達到了前所未有的高度。

哥倫比亞大學計算機科學家Tim Roughgarden在看完論文後直呼：

這也太神奇了，我無法想像還有比這更吸引人的研究。

據悉，這篇論文已經斬獲下週即將舉辦的理論計算機頂會FOCS 2024（計算機科學基礎研討會）的最佳論文。

一言蔽之，現在的Dijkstra算法，已經被證明是解決單源最短路徑問題的「近乎理想」的方法。

那麼這項研究又是如何證明和優化的呢？

70年經典算法新突破

首先，我們先通過一個例子，簡單回顧一下Dijkstra算法。

如下圖所示，Dijkstra算法尋找最短路徑的方法，大致可以分為四步：

從起點出發：選擇起點A。計算從A到鄰近點的距離，例如到B的距離為1，到C的距離為5。選擇較短的路徑，即先前往B。

繼續探索：從新的點（B）繼續查找鄰近點的距離，並將這些距離加上從A到B的距離。例如，從A到B的距離是1，B到D的距離是1，因此A到D的總距離為2（1 + 1 = 2）。更新已知的最短路徑。

記錄新的最短路徑：在探索過程中發現更短的路徑時，更新記錄。例如，A到C的原始距離是5，但通過B和D的路徑到C的總距離是3（1 + 1 + 1 = 3），比原來的距離短，因此更新A到C的距離為3。

重覆步驟，直到覆蓋所有點：算法繼續遍曆，直到所有節點的最短路徑都被確定。每次優先選擇距離最短的路徑進行下一步計算，逐步優化到每個點的最短路徑。

最終，Dijkstra算法可以快速找到網絡中從起始點到其他所有節點的最短路徑。

在最初的Dijkstra算法論文中使用到了一個簡單且關鍵的數據結構——堆（Heap），而這就為後來的計算機科學家們留下了改進的餘地。

例如1984年，兩位計算機科學家設計了一種巧妙的堆數據結構，使得Dijkstra算法在解決單源最短路徑問題所需的時間上達到了理論極限或「下限」。

從某種特定意義上說，這個版本的Dijkstra算法已經可以說是最好的，也是近40年來的一種「標準」。

而這次的最新論文，研究人員的突破口依舊是這個堆數據結構。

因為他們發現，像Fibonacci堆等常用的數據結構雖然在理論上具有較好的最壞情況時間複雜度（Worst-case time complexity），但在很多情況下未能充分利用圖的局部結構特性。

這就導致在處理某些類型的圖時，仍然需要高昂的計算代價。

但如果在1984年設計的堆基礎上加入對最近插入項快速訪問的能力，就可以顯著提升算法的效率。

為此，研究人員提出了一種全新的堆數據結構——具備特殊的 「工作集屬性」（Working Set Property） 。

所謂 「工作集屬性」 ，指的是堆能夠充分利用操作的局部性，從而優先處理最近插入的元素，降低提取最小元素的成本。

這個概念類似於我們在管理待辦事項時，會優先處理那些剛剛添加的緊急任務，從而更高效地完成工作。

若是用公式化的表述，就如下圖所示。

對於在堆中插入並隨後被提取的任意元素x，其工作集Wx包括了在x被插入後、在x被提取後上入的所有元素，以及x本身。

借助這種「工作集屬性」，新設計的堆數據結構能夠顯著提升Dijkstra算法的整體性能，尤其是在具有局部性特徵的圖上。

也成功使Dijkstra算法具備了普遍最優性，不僅在最壞情況下具有最優性，還能在任何圖結構上表現出色。

不僅如此，這項工作還提供了精確的複雜度分析。

例如，作者證明了Dijkstra算法在具有工作集屬性的堆上的比較次數是O(OPTQ(G)+n+max⁡w∈WG∣FG,w∣)。

其中，OPTQ(G)是解決距離排序問題的最優算法所需的比較次數，n是頂點數，∣FG,w∣是前向邊的數量。

這也為算法的性能提供了更精確的界限。

總而言之，這些成果不僅推動了圖算法的研究，也為實際應用中的算法設計提供了新的視角和工具。

喝咖啡時誕生的算法

關於Dijkstra算法誕生的故事，其實是始於一次意外的靈感。

1956年，年僅26歲的荷蘭計算機科學家Edsger Dijkstra當時正試圖為一台新型計算機ARMAC編寫一個程序，來展示它的計算能力。

有一天，他和未婚妻在阿姆斯特丹購物時走進了一家咖啡館，正是在休息的片刻中，Dijkstra突然有了靈感，想出了一個計算最短路徑的算法。

在沒有紙和筆的情況下，他花了大約20分鐘在腦海中推演出了這個算法的細節。

正如他在晚年一次採訪中所說的那樣：

沒有紙筆的情況下，你幾乎被迫避免所有可以避免的複雜性。

也正是這種簡潔和優雅，使得Dijkstra算法在隨後的幾十年里成為計算機科學領域的經典。

Edsger Dijkstra可以說是一位極具影響力的計算機科學家，他不僅以其最短路徑算法聞名，還對計算機科學的許多基礎領域做出了開創性的貢獻。

Dijkstra出生於1930年，父親是一位化學家，母親是一位出色的數學家。

1951 年，Dijkstra在父親的建議下前往劍橋參加了一門為期三週的編程課程，這次經歷改變了他的職業軌跡。

在此期間，他遇到了著名的數學家和計算機科學家Adriaan van Wijngaarden，並由此獲得了在阿姆斯特丹數學中心（Mathematical Centre）的工作機會。

Dijkstra是荷蘭首位以「程序員」身份被僱傭的人，1956年完成學業後，他繼續在數學中心工作，並於1959年發表了他的著名論文A Note on Two Problems in Connexion with Graphs。

這篇論文介紹了他提出的最短路徑算法，後來成為了計算機科學中引用次數最多的論文之一。

儘管Dijkstra的算法十分優雅，但當時幾乎沒有計算機科學期刊，發表過程十分困難，最終他選擇將其發表於新創刊Numerische Mathematik上。

Dijkstra在職業生涯中贏得了極高的聲譽，並於1972年獲得計算機科學領域最負盛名的圖靈獎。

他不僅在編程語言、操作系統和併發控制等領域做出了許多基礎性貢獻，還以其對編程方法學的深入思考而著稱。

他強調程序的正確性，認為程序應該從一開始就正確地設計，而不是通過調試來達到正確。

不過與此同時，Dijkstra的性格也非常獨特，他既被讚賞也被批評，是一位充滿爭議的人物。

他對於計算機科學的教育和研究有著強烈的觀點，常常發表極具挑戰性的言論。

例如，他反對使用goto語句，並在1968年發表了著名的文章Go To Statement Considered Harmful，這篇文章引發了廣泛的爭議，但最終他的觀點得到了普遍認可。

Dijkstra算法不僅可以計算從起始點到一個目的地的最短路徑，還可以給出從起始點到所有其他節點的排序，這正是單源最短路徑問題的解決方案。

它的核心思想是不斷探索當前距離最短的路徑，更新每個節點的最短距離，直到所有節點的距離都確定下來。

這種算法的簡潔性和高效性使得它成為經典的路徑規劃工具。

麻省理工學院的計算機科學家Erik Demaine曾評論道：

這是一個偉大的算法，速度非常快，簡單易實現。

但算法的成功不僅歸功於其核心思想，還離不開數據結構的選擇，在幾十年的發展中，研究人員不斷改進堆數據結構，使得算法的整體性能不斷提升。

而這一次，改良堆數據結構，可以說是再次立功了。

論文地址：

https://arxiv.org/abs/2311.11793

參考鏈接：

[1]https://www.quantamagazine.org/computer-scientists-establish-the-best-way-to-traverse-a-graph-20241025/

[2]https://inference-review.com/article/the-man-who-carried-computer-science-on-his-shoulders