迪傑斯特拉演算法解析

一.理論基礎

迪傑斯特拉演算法（下文簡稱 DJ 演算法）的理論基礎是一條簡單的定理：

下一條最短路徑或者是弧 (V0, Vx)，或者是中間經過 S 中的某些頂點，而後到達 Vx 的路徑。（S 是最短路徑已知的頂點集合）

（為了準確地描述定理，這裡就直接摘抄了。。至於它對不對，嗯，據說反證法可證之）很明顯這是一個遞推演算法：反覆求下一條，直至沒有下一條為止。

二.問題分析

現有加權有向圖如下：

求從 V0 出發，到達其它各個頂點的最短路徑。

首先為了把它轉換成便於描述的數學形式，得寫出對應的鄰接矩陣（x 表示不可達）：

0	50	10	x	45	x
x	0	15	x	10	x
20	x	0	15	x	x
x	20	x	0	35	x
x	x	x	30	0	x
x	x	x	3	x	0

分析定理可以得出：目前 S 集合中只有 1 個頂點：V0（V0 到自身的肯定是最短路徑），除了 S 集合這個輔助空間外，我們還需要：

• V 集合：最短路徑未知的頂點組成的集合，即 S 集合的補集
• path[]：記錄最短路徑，用來顯示結果
• dist[]：記錄路徑長度，作用同上
• Vx：記錄下一個頂點

準備工作結束，可以開始求解了

三.求解過程

0.初始狀態

dist[] 初始化為 V0 到各個頂點的直接距離（x 表示不可直達），path[] 初始化為對應的路徑，不可直達的記作 NULL，選取 V 集合中 dist 值最小的頂點 V2 作為下一個頂點（定理中的 Vx）

1.第 1 步

把 V2 加入 S 集合，我們多了一個中轉站 V2，接下來更新 dist[]，看借助 V2 中轉的話是不是更短，根據計算結果更新 dist[] 和 path[]，把更短的路徑長度和對應路徑放進去，V 集合中 dist 值最小的 V3 作為下一個頂點

2.第 2-5 步

繼續選取下一個頂點，直至 V 集合中沒有可選頂點為止

四.總結

DJ 演算法過程非常簡單：

1. 確定 S 中的第一個點（也就是源點 V0）；
2. 根據定理遞推（一直找最短，並試圖借助最短中轉）

演算法思路本身不難，當初看不明白是因為被具體的偽代碼實現繞進去了，所以學習演算法應該關注思路而不是具體實現，尤其是偽代碼演算法，通常會隨意聲明一些奇怪的資料結構，卻不解釋為什麼需要這些輔助空間，比如本例中，S 集合和 V 集合只需要有一個即可，path[] 和 dist[] 也可以用結構體清晰地表示出來，但偽代碼中零零散散地全都用到了，過多的輔助空間反而妨礙了理解演算法本身。備忘。