戴克斯特拉演算法

戴克斯特拉演算法（英語：Dijkstra's algorithm）， 閣稱迪傑斯特拉演算法、Dijkstra 演算法，是由荷蘭電腦科學家艾茲爾 ・ 戴克斯特拉佇一九五六年發現的演算法，並且三年後佇期刊上發表。戴克斯特拉演算法使用類似廣度優先搜揣的方法解決賦權圖的單源上短路徑問題。

該演算法存在足濟變體：戴克斯特拉的原始版本干焦適用著兩个頂點之間的上短路徑，閣較捷看著的變體固定一个頂點做一个源結點然後揣著該頂點著圖中所有其他結點的上短路徑，產生一个上短路徑樹。

該演算法解決矣圖 $ G=\ langle V , E \ rangle $ 上帶權的單源上短路徑問題。具體來講，戴克斯特拉演算法設定一頂點集合 $ S $，佇咧集合 $ S $ 中所有的頂點佮源點 $ s $ 之間的最終最短路徑權值均已經確定。演算法反匼選擇上短路徑估計上細的點 $ u \ in { V-S } $ 並將 $ u $ 加入 $ S $ 中。該演算法定用路由演算法抑是做其他的圖演算法的一个模組。比如講伊，若圖內底的頂點表示城市，所以面上的權重表示城市間開車經過的距離，該演算法會當用來揣著兩个城市之間的上短路徑。

應當注意，真大多數的戴克斯特拉演算法袂當有效處理帶有負權邊的圖。

戴克斯特拉演算法佇咧電腦科學的人工智慧等領域也予人稱做攏一開銷搜尋，並且予人認為是上良優先搜揣的一个特例。

演算法描述

戴克斯特拉演算法通過保留目前為止所揣著的每一个頂點 $ v \ in V $ 對 $ s $ 到 $ v $ 的上短路徑來做工課。初初的時陣，原點 $ s $ 的路徑權重被去予零開（即原點的實際上短路徑=零）。 同時共所有其他頂點的路徑長度設為不窮大，就表示咱毋知影任何通向遮的頂點的路徑。做演算法結束的時陣，$ d [v] $ 中儲存的便是對 $ s $ 到 $ v $ 的上短路徑，或者是若是路草無存在的話是無窮大。

鹿楝操作是戴克斯特拉演算法的基礎操作：若佇咧一條對 $ u $ 到 $ v $ 的邊仔，遐爾仔對 $ s $ 到 $ v $ 的一條新路徑是將邊 $ w ( u , v ) \ in E $ 添到對 $ s $ 到 $ u $ 的路徑尾部來拓展一條對 $ s $ 到 $ v $ 的路徑。這條路徑的長度是 $ d [u] + w ( u , v ) $。若這个值比目前已經知的 $ d [v] $ 的值愛細，若按呢會當用這个值來代替當前 $ d [v] $ 中的值。鹿楝邊的操作一直執行到所有的 $ d [v] $ 攏是代表對 $ s $ 到 $ v $ 的上短路徑的長度值。

演算法維護兩个頂點集合 $ S $ 和 $ Q $。集合矣 $ S $ 保留所有已經知實際上短路徑值的頂點，來集合 $ Q $ 著愛保留其他的所有頂點。集合矣 $ S $ 初狀態做空，若尾每一步攏有一个頂點對 $ Q $ 徙振動甲 $ S $。這个予選擇的頂點是 $ Q $ 中擁有上細的 $ d [u] $ 值的頂點。做一个頂點 $ u $ 對 $ Q $ 予中轉移到矣 $ S $ 中，演算法著 $ u $ 逐條外接邊 $ w ( u , v ) $ 進行鹿楝。

《 演算法導論》中央出了以下虛擬碼：該虛擬碼計算並保留圖 $ G $ 中原點 $ s $ 到每一頂點 $ v $ 的上短距離 $ d [v] $。其中，函式 $ Extract-Min ( Q ) $ 共頂點集合 $ Q $ 中有上細漢 $ d [u] $ 值的頂點 $ u $ 對 $ Q $ 中刣除閣倒轉來 $ u $。

` ` ` 一functionDijkstra ( G , w , s ) 二   INITIALIZE-SINGLE-SOURCE ( G , s ) / / 實際上的操作是將每一个除原點外的頂點的 $ d [v] $ 置做無窮地，$ d [s]=零 $ 三   $ S \ leftarrow \ emptyset $ 四   $ Q \ leftarrow s $                 / / $ Q $ 是頂點 $ V $ 的一个優先佇列，以頂點的上短路徑估計排序五   while ( $ Q \ not=\ emptyset $ ) 六       do $ u \ leftarrow EXTRACT-MIN ( Q ) $ / / 選取 $ u $ 為 $ Q $ 中上短路徑估計上細的頂點七 $ S \ leftarrow S \ cup u $ 八 for each vertex v $ \ in Adj [u] $ 九           do RELAX ( u , v , w )       / / 鹿成功的結點會予人加入來佇列中 ` ` `

若阮干焦對佇咧 $ s $ 和 $ t $ 中間走揣一條上短路徑的話，阮會使佇第五抑是第六行添加條件若滿足 $ u=t $ 終止程式。

佇咧肯尼 ・ 羅森所對的《離散數學佮其應用》著予出了如下的另外一份虛擬碼：

` ` ` 一procedureDijkstra ( G：邊全為正權的圖） 二   { G 帶有頂點 $ a=v _ { 零 } , v _ { 一 } , v _ { 二 } . . . $ 佮若干邊仔 $ w ( v _ { i } , v _ { j } ) $ } 三     for $ i :=一 $ to n 四         $ D ( v _ { i } ) :=\ infty $ 五     $ D ( a ) :=零 $ 六     $ S :=\ emptyset $ 七     while $ z \ notin S $ 八     begin 九      $ u :=$ 無屬於 $ S $ 的 $ D ( u ) $ 上細的一个頂點十         $ S :=S \ cup \ { u \ } $ 十一         for 所有無屬於 $ S $ 的頂點 $ v $ 十二             if $ D ( u ) + w ( u , v ) < D ( v ) $ then $ D ( v ) :=D ( u ) + w ( u , v ) $ 十三     end { $ D ( z )=$ 對 a 到 z 的上短路長度 } ` ` `

時間複雜度

咱會當用大 O 符號將演算法的運行時間表示為邊數 $ | E | $ 佮頂點數 $ | V | $ 的函式。

對任何因為頂點集 $ Q $ 的實現，演算法的執行時間是 $ O ( | E | \ cdot dk _ { Q } + | V | \ cdot em _ { Q } ) $，其中 $ dk _ { Q } $ 和 $ em _ { Q } $ 分別表示完成鍵的降序排列時間佮 $ Q $ 中提上細的閣再值的時間。

對無任何最佳化的戴克斯特拉演算法，實際上等價數佇每一遍歷了規个圖的所有結點來揣著 Q 中滿足條件的元素（即走揣上細的頂點是 $ O ( | V | ) $ 的）， 另外實際上閣需要遍歷所有的邊一遍，所以演算法的複雜度是 $ O ( | V | ^ { 二 } + | E | ) $。

對邊數減於 $ | V | ^ { 二 } $ 的疏圖來講，會當用鄰接表來閣較有效的實現該演算法。

會用得使用一个二元堆積抑是斐波納契堆用做優先隊列來走揣上細的頂點（$ Extract-Min $）以最佳化演算法。用著二元堆積的時陣，演算法所需要的時間為 $ O ( ( | E | + | V | ) \ log | V | ) $，斐波納契堆能提懸一寡效能，予演算法運行時間達到 $ O ( | E | + | V | \ log | V | ) $。毋過，使用斐波納契堆進行編程，有時會因為演算法定定算傷過大而且速度無顯明提懸。

下跤是一寡戴克斯特拉演算法經典實現的複雜度較：

演算法正確性證明

戴克斯特拉本人佇伊的論文中共出一份簡單的證明。

《 演算法導論》用回轉不變式（數學歸納法）予出了如下的一份證明：

知影一帶權圖 $ G=< V , E > $，其加權函式 $ w $ 的值非負，源點為 $ s $。嘿該圖執行戴克斯特拉演算法，嘿所有 $ u \ in V $ 有 $ d [u]=\ delta ( s , u ) $。其中 $ d [u] $ 表示 u 點的上短路徑估計，$ \ delta ( s , u ) $ 表示 $ s $ 到 $ u $ 點的上短路徑。

證明：證明下的迴箍無變式成隨會當：佇每擺執行 EXTRACT-MIN 時，嘿每一个頂點 $ u \ in S $，有 $ d [u]=\ delta ( s , u ) $ 成隨會當。因為上界的性質，佇咧 $ u $ 加入去矣 $ S $ 了後，若是有 $ d [u]=\ delta ( s , u ) $，佇後壁逐改迴箍內底攏袂改變這个性質。

初初化：第一改回頭前，$ S=\ emptyset $，就按呢迴圈無變式顯然成立。

保持：實際上愛證明每一輪迴箍內底加入到 $ S $ 中的結點滿足 $ d [u]=\ delta ( s , u ) $。利用反證法，準講 $ u $ 是第一个不滿足此條件的結點，考慮迴圈開始進前的狀況，首先 $ u $ 一定無等於 $ s $，這是顯然的。其次 $ s $ 一定有到 $ u $ 的路徑，抑無這路草是散赤大。遐爾仔假佇咧 $ u $ 進入的時陣，有上短路徑 $ p=s-> u $，假使這个路徑存在兩个點按呢 $ x $，$ y $。$ y \ in V-S $、$ x \ in S $，而且 x 是 y 的前驅，路徑 $ p $ 會當分解為講 $ s-p _ { 一 }-> x-> y-p _ { 二 }-> u $（此處 $-p _ { 一 }-> $ 表示講經過 $ p _ { 一 } $ 這條路徑，後仝）， 其中路徑 $ p _ { 一 } $ 佮路徑 $ p _ { 二 } $ 會當為空。因為 $ u $ 是第一个無滿足 $ d [u]=\ delta ( s , u ) $ 的，閣因為 $ x $ 是滿足該條件的，而且 $ ( x , y ) $ 一定已經予人鹿楝過矣，所以乎 $ y $ 是滿足該條件的。

這馬只要推出矛盾，即可證明 u 無存在：$ y $ 佇咧 $ u $ 進前出現，而且圖中所有權值非負，所以有 $ \ delta ( s , y ) \ leq \ delta ( s , u ) $，所以乎：

$ d [y] \ leq \ delta ( s , y ) \ leq \ delta ( s , u ) \ leq d [u] $，但是因為 $ u $ 和 $ y $ 同時佇咧 $ V-S $ 中，所以 $ d [u] \ leq d [y] $，因此必有 $ d [y]=\ delta ( s , y )=\ delta ( s , u )=d [u] $，就證明矣 $ u $ 點無可能不滿足該條件，欲講假做假做假，原命題著證。

終止：終止時，$ Q=\ emptyset $，因為 $ Q=V-S $，所以 $ V=S $，因此對所有 $ u \ in V $ 有 $ d [u]=\ delta ( s , u ) $。

演算法起源佮歷史

> 對鹿特丹到格羅寧根的上短路徑是啥物？實際上，這就是對著任意兩座城市之間的最短路問題。解決這个問題實際上大概干焦開我二十分鐘：一工透早，我佮我的未婚妻佇阿姆斯特丹買物件，忝矣，咱便坐佇咖啡館的露台頂懸啉咖啡，閣來我就試一下毋會使用一个演算法解決最短路的問題。正如我咧講，這是一个二十分鐘的發現。毋過實際上，我佇三年後的一九五九年才共這个演算法發表佇論文上。就算這馬來看這篇論文的可讀性嘛蓋懸，這个演算法之所以遮優雅，其中一个原因就是我無用筆紙設計了伊。尾仔我才知影講，無用筆紙設計的優點之一是你不得不避免所有可避免的複雜問題。予我驚疑的是，這个演算法上尾成做我成名的基石之一。 > >

戴克斯特拉一九五六年佇荷蘭數學佮電腦科學研究學會擔任程式設計師時為著展示新型電腦 ARMAC 的功能捌思考過上短路徑問題的解法。伊的目標是予袂去實際計算的人嘛會當理解這个問題佮解決的方法，所以伊咧發現矣這个演算法了後佇 ARMAC 最做了簡單實驗。一九五九年，伊正式共這个演算法發表佇期刊頂懸，這个演算法嘛成做是戴克斯特拉成名的基石之一。

演算法相關應用

鏈路的狀態路由協定當中需要計算上短路的時常用著愛用演算法，該演算法咧開放上短路徑優先佮中央系統到中央系統協定中的相關應用是其在網路由中的典型實現。

戴克斯特拉演算法佮改進演算法應用廣泛，尤其是咧揣路、交通、規劃中。

若是有已經知資訊會當用來估計某一點到目標點的距離，著愛改用 A \ * 搜揣演算法，以減小上短路徑的搜揣範圍，戴克斯特拉演算法本身嘛會使看做是 A \ * 搜揣演算法的一个特例。

戴克斯特拉演算法本身採用矣佮 Prim 演算法類似的貪心策略。快速行進演算法佮戴克斯特拉演算法仝款有相𫝛的所在。

參考源程式

以下是該演算法使用堆最佳化的一个 C + + 實現參考：

以下是該演算法 Python 的一个實現 :

參見

• 圖論
• A \ * 搜揣演算法
• 貝爾曼-福特演算法
• 闊度優先搜揣
• Flood fill
• Floyd-Warshall 演算法
• 上長路徑問題

外部連結

• 迪科斯徹演算法分解演示影片（優酷）
• Animation of Dijkstra's algorithm
• The Boost Graph Library ( BGL )
• Interactive Implementation of Dijkstra's Algorithm
• Shortest Path Problem : Dijkstra's Algorithm
• Dijkstra 演算法使用 TDD 的一个實現
• Graphical explanation of Dijkstra's algorithm step-by-step on an example