目錄

一、算法思想

二、算法詳細步驟

三、偽代碼 + C++代碼

四、算法復雜度分析

五、算法改進

六、應用案例

---

一、算法思想

1、Dijkstra 算法是用來求解單源最短路徑問題的經(jīng)典算法，其本質(zhì)上是一個貪心算法。

? ?（PS: 求任意兩個結點之間最短路徑的有 Floyd 算法）

2、算法的基本思想是：設置一個頂點集合 S?并不斷地做貪心選擇來擴充這個集合。

3、該算法適用：1）邊權為正，2）有向無向都適用。

有一些相關的性質(zhì)：

對于邊權為正的圖，任意兩個結點之間的最短路，不會經(jīng)過重復的結點。

對于邊權為正的圖，任意兩個結點之間的最短路，不會經(jīng)過重復的邊。

對于邊權為正的圖，任意兩個結點之間的最短路，任意一條的結點數(shù)不會超過 n ，邊數(shù)不會超過 n - 1 。

?

二、算法詳細步驟

假設：

? ? ? ? 1）已知帶權圖 G = (V, E)

? ? ? ?-?V: 頂點(Vertex)的集合

? ? ? ?-?E: 邊(Edge)的集合

? ? ? ? ? ? ? ? ? ? ? -?邊 e = (u, v), u??V, v??V

? ? ? ? 2）一個頂點屬于S當且僅當從源到該頂點的最短路徑長度已知。

? ? ? ? 3)? 數(shù)據(jù)結構：數(shù)組d，為記錄當前每個頂點所對應的最短特殊路徑長度（源v0到該頂點）。

算法步驟：

1、S 中初始時僅包含源 v0

2、從頂點集合 { V - S } 中選取最短特殊路徑長度最短的頂點，并將其加入 S

3、對數(shù)組 d 進行更新（更新條件：若源 v0 通過某個頂點到該頂點的路徑比原先 d 數(shù)組保存的小）

?

三、偽代碼 + C++代碼

1、偽代碼

清除所有點的標號 // 屬于集合S的標記 設d[0] = 0， 其他d[i] = INF // initial 循環(huán)n次 {在所有未標號結點中，選出d值最小的結點x // 從{V - S}中選出從源出發(fā)距離最短的頂點給結點x標記 // 加入集合S對于從x出發(fā)的所有邊（x，y），更新d[y] = min{d[y], d[y]+w(x, y)}? // 更新所有x的出邊頂點 }?

?

2、C++代碼實現(xiàn)

memset(v, 0, sizeof(v)); for(int i = 0; i < n; i++) d[i] = (i==0 ? 0 : INF); for(int i = 0; i < n; i++) {int x, m = INF;for(int y = 0; y < n; y++) if(!v[y] && d[y]<=m) m = d[x=y];v[x] = 1;for(int y = 0; y < n; y++) d[y] = min(d[y], d[x] + w[x][y]); }

?

四、算法復雜度分析

?

五、算法改進

?

六、應用案例

?

更新：2021年5月3日

未完，待續(xù)。。。

?

?

總結

以上是生活随笔為你收集整理的单源最短路径Dijkstra算法的思想、详细步骤、代码的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。