迪杰斯特拉算法（Dijkstra’s algorithm）以及示例

迪杰斯特拉算法（Dijkstra’s algorithm）是一種非常重要且有價值的算法。它被廣泛應(yīng)用于計算圖中單源最短路徑問題，在交通路線規(guī)劃、網(wǎng)絡(luò)路由、作業(yè)調(diào)度等領(lǐng)域有著廣泛的應(yīng)用。

迪杰斯特拉算法是由荷蘭計算機(jī)科學(xué)家克勞德·迪杰斯特拉(Edsger W. Dijkstra)于1959年首次提出的。這個算法被用來計算單源最短路徑，在圖論和計算機(jī)科學(xué)領(lǐng)域里被廣泛使用。迪杰斯特拉本人在發(fā)明這個算法時是在荷蘭國家電訊公司工作，當(dāng)時他正在研究如何通過計算機(jī)來規(guī)劃路徑。

迪杰斯特拉算法是用于求最短路徑的一種算法。它是貪心算法的一種，通過不斷地選取最短路徑來逼近最終答案。算法流程如下：

1. 初始化所有結(jié)點的最短路徑為無窮大。
2. 設(shè)置起點的最短路徑為 0。
3. 從起點開始，每次選取最短路徑最小的結(jié)點，并將其周圍的結(jié)點的最短路徑更新。

重復(fù)步驟 3，直到所有結(jié)點的最短路徑都被更新。

例子:

假設(shè)有一張圖如下，求從結(jié)點1到結(jié)點4的最短路徑。

初始化最短路徑：

1: 0, 2: inf, 3: inf, 4: inf, 5: inf

設(shè)置起點1的最短路徑為0，并開始更新周圍結(jié)點的最短路徑。

更新 2: 1+2=3, 3: 1+3=4

選擇 2 作為新的當(dāng)前結(jié)點

更新 4: 2+1=3, 5: 2+3=5

選擇 4 作為新的當(dāng)前結(jié)點

更新 5: 4+1=5

選擇 5 作為新的當(dāng)前結(jié)點

最終得到的最短路徑為:1: 0, 2: 3, 3: 4, 4: 3, 5: 5

結(jié)點 1 -> 2 -> 4 -> 5

可以看到結(jié)點1到結(jié)點4的最短路徑為1 -> 2 -> 4，距離為3。

注意迪杰斯特拉算法只適用于有向圖或者邊權(quán)非負(fù)的無向圖，如果邊權(quán)有負(fù)數(shù)，則需要使用其他算法，如貝爾man-福德算法。

迪杰斯特拉算法的最大優(yōu)點是其簡單易懂和時間復(fù)雜度較低，因此在實際應(yīng)用中非常實用。它可以在稠密圖和稀疏圖中使用，對于邊權(quán)均為非負(fù)數(shù)的圖都可以使用。

　　?