整理自《數(shù)據(jù)結(jié)構(gòu)高分筆記》

1、算法基本思想

設(shè)有兩個(gè)頂點(diǎn)集合S和T，集合S中存放圖中已找到最短路徑的頂點(diǎn)，集合T存放圖中剩余頂點(diǎn)。初始狀態(tài)時(shí)，集合S中只包含源點(diǎn)V0，然后不斷從集合T中選取到頂點(diǎn)V0路徑長(zhǎng)度最短的頂點(diǎn)vu并入集合S中，集合S中每新并入一個(gè)頂點(diǎn)，都要修改頂點(diǎn)v0到集合T中頂點(diǎn)的最短路徑的長(zhǎng)度值。不斷重復(fù)此過(guò)程，直到集合T的頂點(diǎn)全部并入到S中為止。

2、例子解析

上面的說(shuō)明可能有些抽象，不過(guò)通過(guò)下面的例子，我相信咱們可以很輕松的明白迪杰斯特拉算法的具體過(guò)程。
我們首先定義三個(gè)數(shù)組：dist[],path[],set[]。
dist[vi]表示當(dāng)前已找到的從v0到每個(gè)終點(diǎn)vi的最短路徑的長(zhǎng)度。它的初態(tài)為：若v0到vi有邊，則dist[vi]為邊上的權(quán)值，否則為無(wú)限大。
path[vi]中保存從v0到vi 最短路徑上vi的前一個(gè)頂點(diǎn)，假設(shè)最短路徑上的頂點(diǎn)序列為v0，v1，v2......vj，vi，則path[vi]=vj，path[]的初態(tài)為，若v0到vi有邊，則path[vi]為v0，否則為-1。
set[]為標(biāo)記數(shù)組，set[vi]=0表示vi在T中，即沒(méi)有被并入最短路徑：set[vi]=1表示vi在S中，即已經(jīng)被并入最短路徑，初始時(shí)set[v0]=1，其他元素均為0.

我們以下面的圖作為例子，來(lái)體會(huì)下迪杰斯特拉算法的執(zhí)行過(guò)程，我們選擇頂點(diǎn)0作為我們的原點(diǎn)：

初始時(shí)：dist數(shù)組：dist[0]=0,dist[1]=4,dist[2]=6,dist[3]=6,其他為∞.path[1]=path[2]=path[3]=1,其他元素為-1，set[0]=1,其余為0。我們用g[I,j]表示從I到j(luò)的邊的權(quán)值。

第一步
從當(dāng)前dist數(shù)組中選擇長(zhǎng)度最短的，即dist[1]=4，所以將頂點(diǎn)1并入S中，set[1]=1，同時(shí)以頂點(diǎn)1為中間節(jié)點(diǎn)檢測(cè)剩余頂點(diǎn)：
dist[2] = 6 > dist[1] + g[1,2] = 4 + 1 = 5，因此dist[2]變?yōu)?，path[2]變?yōu)?，表明要到達(dá)頂點(diǎn)2，上一個(gè)需要到達(dá)的頂點(diǎn)為1。
dist[3]=6 < dist[1] + g[1,3] = ∞,因此dist[3]不變，path[3]不變。
dist[4] = ∞ > dist[1] + g[1,4] = 11,因此dist[4]變?yōu)?1，path[4]變?yōu)?。
dist[5] = ∞ = dist[1] + g[1,5] = ∞,dist[5]不變，path[5]不變。
dist[6] = ∞ = dist[1] + g[1,6] = ∞，dist[6]不變，path[6]不變。

第二步
從當(dāng)前dist數(shù)組中選擇長(zhǎng)度最短的，即dist[2]=5，所以將頂點(diǎn)2并入S中，set[2]=1，同時(shí)以頂點(diǎn)2為中間節(jié)點(diǎn)檢測(cè)剩余頂點(diǎn)（3，4，5，6）：
dist[3] = 6 > dist[2] + g[2,3] =∞ ,因此dist[3]不變，path[3]不變。
dist[4] = 11 = dist[2] + g[2,4]=5 + 6 = 11,因此dist[4]不變，path[4]不變。
dist[5] = ∞ < dist[2] + g[2,5] = 5 + 4 = 9 ,因此dist[5]變?yōu)?，path[5]變?yōu)?。
dist[6] = ∞ = dist[2] + g[2,6] = ∞ ,dist[6]不變，path[6]不變.

第三步
從當(dāng)前dist數(shù)組中選擇長(zhǎng)度最短的，即dist[3]=6，所以將頂點(diǎn)3并入S中，set[3]=1，同時(shí)以頂點(diǎn)2為中間節(jié)點(diǎn)檢測(cè)剩余頂點(diǎn)（4，5，6）：
dist[4] = 11 > dist[3] + g[3,4]=∞,因此dist[4]不變，path[4]不變。
dist[5] = 0 > dist[3] + g[3,5] = 11 ,因此dist[5]不變，path[5]不變.
dist[6] = ∞ = dist[3] + g[3,5] = ∞ ,dist[6]不變，path[6]不變..

第四步
從當(dāng)前dist數(shù)組中選擇長(zhǎng)度最短的，即dist[5]=9，所以將頂點(diǎn)5并入S中，set[5]=1，同時(shí)以頂點(diǎn)2為中間節(jié)點(diǎn)檢測(cè)剩余頂點(diǎn)（4，6）：
dist[4] = 11 < dist[5] + g[5,4] = 10 ,因此dist[4]變?yōu)?0，path[4]變?yōu)?。
dist[6] = ∞ < dist[5] + g[5,6] = 17 ,因此dist[6]變?yōu)?7，path[6]變?yōu)?。

第五步
從當(dāng)前dist數(shù)組中選擇長(zhǎng)度最短的，即dist[4]=10，所以將頂點(diǎn)5并入S中，set[4]=1，同時(shí)以頂點(diǎn)2為中間節(jié)點(diǎn)檢測(cè)剩余頂點(diǎn)（6）：
dist[6] = 17 < dist[4] + g[4,6] = 10 + 6 = 16,因此dist[6]變?yōu)?6，path[6]變?yōu)?。

第六步
從當(dāng)前dist數(shù)組中選擇長(zhǎng)度最短的，即dist[6]=16，所以將頂點(diǎn)5并入S中，set[6]=1，此時(shí)所有的頂點(diǎn)都已經(jīng)并入最短路徑中，所以算法結(jié)束。

此時(shí)，三個(gè)數(shù)組的值分別為：

根據(jù)dist數(shù)組，我們可以知道從v0出發(fā)到各個(gè)頂點(diǎn)的最短路徑的值，根據(jù)path[]數(shù)組，我們可以得到v0出發(fā)到各個(gè)頂點(diǎn)的最短路徑包含的頂點(diǎn)順序，比如我們想要得到從頂點(diǎn)v0 到 v6的最短路徑，我們采用倒推法，因?yàn)閜ath[6] = 4, 可以知道要到頂點(diǎn)6，需要先到頂點(diǎn)4，在根據(jù)path[4] = 5 ,所以需要先到頂點(diǎn)5，以此類推，可以得到從0到6的最短最短路徑為：0 - 1 -2 -5 -4-6.
可以看到通過(guò)迪杰斯特拉算法，我們可以得到從一個(gè)頂點(diǎn)出發(fā)到其他各個(gè)頂點(diǎn)的最短路徑的長(zhǎng)度值和經(jīng)過(guò)的頂點(diǎn)路徑。