時(shí)隔近70年，那個(gè)用來解決最短路徑問題的經(jīng)典算法——Dijkstra，現(xiàn)在有了新突破：

被證明具有普遍最優(yōu)性（Universal Optimality）。

什么意思？

這就意味著不論它面對(duì)多復(fù)雜的圖結(jié)構(gòu)，即便在最壞情況下都能達(dá)到理論上的最優(yōu)性能！

而且這還是學(xué)術(shù)界首次將這一概念應(yīng)用于任何序列算法。

△圖源：Quantamagzine

對(duì)于Dijkstra算法，想必很多人肯定不會(huì)陌生，畢竟它是每個(gè)計(jì)算機(jī)本科生必學(xué)的內(nèi)容。

而且從它誕生至今，已經(jīng)在廣泛地應(yīng)用于我們的日常生活中，例如在谷歌地圖、蘋果地圖，Dijkstra算法就被用來計(jì)算從用戶當(dāng)前位置到目的地的最優(yōu)路線。

在計(jì)算機(jī)網(wǎng)絡(luò)中，被廣泛應(yīng)用于路由協(xié)議中；例如開放最短路徑優(yōu)先（OSPF）協(xié)議就是基于Dijkstra算法來計(jì)算網(wǎng)絡(luò)中數(shù)據(jù)包的最優(yōu)傳輸路徑。

再如通信網(wǎng)絡(luò)設(shè)計(jì)、機(jī)器人路徑規(guī)劃和物流運(yùn)輸優(yōu)化等領(lǐng)域，也是處處都有它的身影。

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

而這項(xiàng)集結(jié)了蘇黎世聯(lián)邦理工、CMU、普林斯頓等頂尖高?？蒲腥藛T之力的研究，一舉讓這個(gè)經(jīng)典算法達(dá)到了前所未有的高度。

哥倫比亞大學(xué)計(jì)算機(jī)科學(xué)家Tim Roughgarden在看完論文后直呼：

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

據(jù)悉，這篇論文已經(jīng)斬獲下周即將舉辦的理論計(jì)算機(jī)頂會(huì)FOCS 2024（計(jì)算機(jī)科學(xué)基礎(chǔ)研討會(huì)）的最佳論文。

一言蔽之，現(xiàn)在的Dijkstra算法，已經(jīng)被證明是解決單源最短路徑問題的“近乎理想”的方法。

那么這項(xiàng)研究又是如何證明和優(yōu)化的呢？

70年經(jīng)典算法新突破

首先，我們先通過一個(gè)例子，簡(jiǎn)單回顧一下Dijkstra算法。

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

1. 從起點(diǎn)出發(fā)：選擇起點(diǎn)A。計(jì)算從A到鄰近點(diǎn)的距離，例如到B的距離為1，到C的距離為5。選擇較短的路徑，即先前往B。
2. 繼續(xù)探索：從新的點(diǎn)（B）繼續(xù)查找鄰近點(diǎn)的距離，并將這些距離加上從A到B的距離。例如，從A到B的距離是1，B到D的距離是1，因此A到D的總距離為2（1 + 1 = 2）。更新已知的最短路徑。
3. 記錄新的最短路徑：在探索過程中發(fā)現(xiàn)更短的路徑時(shí)，更新記錄。例如，A到C的原始距離是5，但通過B和D的路徑到C的總距離是3（1 + 1 + 1 = 3），比原來的距離短，因此更新A到C的距離為3。
4. 重復(fù)步驟，直到覆蓋所有點(diǎn)：算法繼續(xù)遍歷，直到所有節(jié)點(diǎn)的最短路徑都被確定。每次優(yōu)先選擇距離最短的路徑進(jìn)行下一步計(jì)算，逐步優(yōu)化到每個(gè)點(diǎn)的最短路徑。

△圖源：Quantamagzine

最終，Dijkstra算法可以快速找到網(wǎng)絡(luò)中從起始點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。

在最初的Dijkstra算法論文中使用到了一個(gè)簡(jiǎn)單且關(guān)鍵的數(shù)據(jù)結(jié)構(gòu)——堆（Heap），而這就為后來的計(jì)算機(jī)科學(xué)家們留下了改進(jìn)的余地。

例如1984年，兩位計(jì)算機(jī)科學(xué)家設(shè)計(jì)了一種巧妙的堆數(shù)據(jù)結(jié)構(gòu)，使得Dijkstra算法在解決單源最短路徑問題所需的時(shí)間上達(dá)到了理論極限或“下限”。

從某種特定意義上說，這個(gè)版本的Dijkstra算法已經(jīng)可以說是最好的，也是近40年來的一種“標(biāo)準(zhǔn)”。

而這次的最新論文，研究人員的突破口依舊是這個(gè)堆數(shù)據(jù)結(jié)構(gòu)。

因?yàn)樗麄儼l(fā)現(xiàn)，像Fibonacci堆等常用的數(shù)據(jù)結(jié)構(gòu)雖然在理論上具有較好的最壞情況時(shí)間復(fù)雜度（Worst-case time complexity），但在很多情況下未能充分利用圖的局部結(jié)構(gòu)特性。

這就導(dǎo)致在處理某些類型的圖時(shí)，仍然需要高昂的計(jì)算代價(jià)。

但如果在1984年設(shè)計(jì)的堆基礎(chǔ)上加入對(duì)最近插入項(xiàng)快速訪問的能力，就可以顯著提升算法的效率。

為此，研究人員提出了一種全新的堆數(shù)據(jù)結(jié)構(gòu)——具備特殊的 “工作集屬性”（Working Set Property） 。

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

這個(gè)概念類似于我們?cè)诠芾泶k事項(xiàng)時(shí)，會(huì)優(yōu)先處理那些剛剛添加的緊急任務(wù)，從而更高效地完成工作。

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

對(duì)于在堆中插入并隨后被提取的任意元素x，其工作集W_x包括了在x被插入后、在x被提取前插入的所有元素，以及x本身。

借助這種“工作集屬性”，新設(shè)計(jì)的堆數(shù)據(jù)結(jié)構(gòu)能夠顯著提升Dijkstra算法的整體性能，尤其是在具有局部性特征的圖上。

也成功使Dijkstra算法具備了普遍最優(yōu)性，不僅在最壞情況下具有最優(yōu)性，還能在任何圖結(jié)構(gòu)上表現(xiàn)出色。

不僅如此，這項(xiàng)工作還提供了精確的復(fù)雜度分析。

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

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

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

總而言之，這些成果不僅推動(dòng)了圖算法的研究，也為實(shí)際應(yīng)用中的算法設(shè)計(jì)提供了新的視角和工具。

喝咖啡時(shí)誕生的算法

關(guān)于Dijkstra算法誕生的故事，其實(shí)是始于一次意外的靈感。

1956年，年僅26歲的荷蘭計(jì)算機(jī)科學(xué)家Edsger Dijkstra當(dāng)時(shí)正試圖為一臺(tái)新型計(jì)算機(jī)ARMAC編寫一個(gè)程序，來展示它的計(jì)算能力。

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

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

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

沒有紙筆的情況下，你幾乎被迫避免所有可以避免的復(fù)雜性。

也正是這種簡(jiǎn)潔和優(yōu)雅，使得Dijkstra算法在隨后的幾十年里成為計(jì)算機(jī)科學(xué)領(lǐng)域的經(jīng)典。

Edsger Dijkstra可以說是一位極具影響力的計(jì)算機(jī)科學(xué)家，他不僅以其最短路徑算法聞名，還對(duì)計(jì)算機(jī)科學(xué)的許多基礎(chǔ)領(lǐng)域做出了開創(chuàng)性的貢獻(xiàn)。

Dijkstra出生于1930年，父親是一位化學(xué)家，母親是一位出色的數(shù)學(xué)家。

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

在此期間，他遇到了著名的數(shù)學(xué)家和計(jì)算機(jī)科學(xué)家Adriaan van Wijngaarden，并由此獲得了在阿姆斯特丹數(shù)學(xué)中心（Mathematical Centre）的工作機(jī)會(huì)。

Dijkstra是荷蘭首位以“程序員”身份被雇傭的人，1956年完成學(xué)業(yè)后，他繼續(xù)在數(shù)學(xué)中心工作，并于1959年發(fā)表了他的著名論文A Note on Two Problems in Connexion with Graphs。

這篇論文介紹了他提出的最短路徑算法，后來成為了計(jì)算機(jī)科學(xué)中引用次數(shù)最多的論文之一。

盡管Dijkstra的算法十分優(yōu)雅，但當(dāng)時(shí)幾乎沒有計(jì)算機(jī)科學(xué)期刊，發(fā)表過程十分困難，最終他選擇將其發(fā)表于新創(chuàng)刊Numerische Mathematik上。

Dijkstra在職業(yè)生涯中贏得了極高的聲譽(yù)，并于1972年獲得計(jì)算機(jī)科學(xué)領(lǐng)域最負(fù)盛名的圖靈獎(jiǎng)。

他不僅在編程語(yǔ)言、操作系統(tǒng)和并發(fā)控制等領(lǐng)域做出了許多基礎(chǔ)性貢獻(xiàn)，還以其對(duì)編程方法學(xué)的深入思考而著稱。

他強(qiáng)調(diào)程序的正確性，認(rèn)為程序應(yīng)該從一開始就正確地設(shè)計(jì)，而不是通過調(diào)試來達(dá)到正確。

不過與此同時(shí)，Dijkstra的性格也非常獨(dú)特，他既被贊賞也被批評(píng)，是一位充滿爭(zhēng)議的人物。

他對(duì)于計(jì)算機(jī)科學(xué)的教育和研究有著強(qiáng)烈的觀點(diǎn)，常常發(fā)表極具挑戰(zhàn)性的言論。

例如，他反對(duì)使用goto語(yǔ)句，并在1968年發(fā)表了著名的文章Go To Statement Considered Harmful，這篇文章引發(fā)了廣泛的爭(zhēng)議，但最終他的觀點(diǎn)得到了普遍認(rèn)可。

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

它的核心思想是不斷探索當(dāng)前距離最短的路徑，更新每個(gè)節(jié)點(diǎn)的最短距離，直到所有節(jié)點(diǎn)的距離都確定下來。

這種算法的簡(jiǎn)潔性和高效性使得它成為經(jīng)典的路徑規(guī)劃工具。

麻省理工學(xué)院的計(jì)算機(jī)科學(xué)家Erik Demaine曾評(píng)論道：

這是一個(gè)偉大的算法，速度非?？欤?jiǎn)單易實(shí)現(xiàn)。

但算法的成功不僅歸功于其核心思想，還離不開數(shù)據(jù)結(jié)構(gòu)的選擇，在幾十年的發(fā)展中，研究人員不斷改進(jìn)堆數(shù)據(jù)結(jié)構(gòu)，使得算法的整體性能不斷提升。

而這一次，改良堆數(shù)據(jù)結(jié)構(gòu)，可以說是再次立功了。

論文地址：https://arxiv.org/abs/2311.11793