Dijkstra算法

**戴克斯特拉演算法**（英語：Dijkstra's algorithm），又稱**迪傑斯特拉演算法**、**Dijkstra 演算法**，是由荷蘭電腦科學家艾茲赫爾・戴克斯特拉在 1956 年發現的演算法，並於 3 年後在期刊上發表。戴克斯特拉演算法使用類似廣度優先搜尋的方法解決賦權圖的單源最短路徑問題。

該演算法存在很多變體：戴克斯特拉的原始版本僅適用於找到兩個頂點之間的最短路徑，後來更常見的變體固定了一個頂點作為源結點然後找到該頂點到圖中所有其它結點的最短路徑，產生一個最短路徑樹。

該演算法解決了圖 $G=\langle V,E\rangle $ 上帶權的單源最短路徑問題。具體來說，戴克斯特拉演算法設定了一頂點集合 $S$ ，在集合 $S$ 中所有的頂點與源點 $s$ 之間的最終最短路徑權值均已確定。演算法反覆選擇最短路徑估計最小的點 $u\in {V-S}$ 並將 $u$ 加入 $S$ 中。該演算法常用於路由演算法或者作為其他圖演算法的一個子模組。舉例來說，如果圖中的頂點表示城市，而邊上的權重表示城市間開車行經的距離，該演算法可以用來找到兩個城市之間的最短路徑。

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

戴克斯特拉演算法在電腦科學的人工智慧等領域也被稱為均一開銷搜尋，並被認為是最良優先搜尋的一個特例。

## 演算法描述

戴克斯特拉演算法通過保留目前為止所找到的每個頂點 $v\in V$ 從 $s$ 到 $v$ 的最短路徑來工作。初始時，原點 $s$ 的路徑權重被賦為 0 （即原點的實際最短路徑 = 0）。同時把所有其他頂點的路徑長度設為無窮大，即表示我們不知道任何通向這些頂點的路徑。當演算法結束時， $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$ 。

```
 1  **function** Dijkstra(G, w, s)
 2   INITIALIZE-SINGLE-SOURCE(G, s)                //實際上的操作是將每個除原點外的頂點的$d[v]$置為無窮大，$d[s]=0$
 3   $S\leftarrow \emptyset $
 4   $Q\leftarrow s$                                //$Q$是頂點$V$的一個優先佇列，以頂點的最短路徑估計排序
 5   while($Q\not =\emptyset $)
 6       do $u\leftarrow EXTRACT-MIN(Q)$          //選取$u$為$Q$中最短路徑估計最小的頂點
 7       $S\leftarrow S\cup u$
 8       for each vertex v $\in Adj[u]$
 9            do RELAX(u, v, w)            //鬆弛成功的結點會被加入到佇列中
```

如果我們只對在 $s$ 和 $t$ 之間尋找一條最短路徑的話，我們可以在第 5 或第 6 行添加條件如果滿足 $u=t$ 的話終止程式。

在肯尼・羅森所著的《離散數學及其應用》中給出了如下的另一份虛擬碼：

```
 1 **procedure** Dijkstra(G：邊全為正權的圖）
 2   {G帶有頂點$a=v_{0},v_{1},v_{2}...$和若干邊$w(v_{i},v_{j})$}
 3    for $i:=1$ to n
 4       $D(v_{i}):=\infty $
 5    $D(a):=0$
 6    $S:=\emptyset $
 7    while $z\notin S$
 8    begin
 9          $u:=$不屬於$S$的$D(u)$最小的一個頂點
 10        $S:=S\cup \{u\}$
 11        for 所有不屬於$S$的頂點$v$
 12            if $D(u)+w(u,v)<D(v)$ then $D(v):=D(u)+w(u,v)$
 13    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|^{2}+|E|)$ 。

對於邊數少於 $|V|^{2}$ 的稀疏圖來說，可以用鄰接表來更有效的實現該演算法。

可以使用一個二元堆積或者斐波納契堆用作優先隊列來尋找最小的頂點（ $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_{1}->x->y-p_{2}->u$ （此處 $-p_{1}->$ 表示經過 $p_{1}$ 這條路徑，後同），其中路徑 $p_{1}$ 和路徑 $p_{2}$ 可以為空。由於 $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)$ 。

## 演算法起源與歷史

> 從鹿特丹到格羅寧根的最短路徑是什麼？實際上，這就是對於任意兩座城市之間的最短路問題。解決這個問題實際上大概只花了我 20 分鐘：一天早上，我和我的未婚妻在阿姆斯特丹購物，累了，我們便坐在咖啡館的露台上喝咖啡，然後我就試了一下能否用一個演算法解決最短路問題。正如我所說，這是一個 20 分鐘的發現。不過實際上，我在 3 年後的 1959 年才把這個演算法發表在論文上。即使現在來看這篇論文的可讀性也非常高，這個演算法之所以如此優雅，其中一個原因就是我沒用筆紙就設計了它。後來我才知道，沒用筆紙設計的優點之一是你不得不避免所有可避免的複雜問題。令我驚訝的是，這個演算法最終成為我成名的基石之一。
> 
> 

戴克斯特拉 1956 年在荷蘭數學和電腦科學研究學會擔任程式設計師時為了展示新型電腦 ARMAC 的功能曾思考過最短路徑問題的解法。他的目標是讓不去實際計算的人也能理解這個問題和解決的方法，於是他在發現了這個演算法之後在 ARMAC 上做了簡單實驗。1959 年，他正式將此演算法發表在期刊上，該演算法也成為了戴克斯特拉成名的基石之一。

## 演算法相關應用

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

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

如果有已知資訊可用來估計某一點到目標點的距離，則可改用 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 （頁面存檔備份，存於網際網路檔案館）