????給定有向帶權(quán)圖G = ( V, E ),其中每條邊的權(quán)是非負(fù)實(shí)數(shù)。此外，給定V中的一個(gè)頂點(diǎn)，稱為源點(diǎn)。現(xiàn)在要計(jì)算從源點(diǎn)到所有其他頂點(diǎn)的最短路徑長度，這里路徑長度指路上各邊的權(quán)之和。

????如何求源點(diǎn)到其他各頂點(diǎn)的最短路徑呢？

Dijkstra算法采用的貪心策略是選擇特殊路徑長度最短的路徑，將其連接的V-S中的頂點(diǎn)加入到集合S中，同時(shí)更新數(shù)組dist[ ]。一旦S包含了所有的頂點(diǎn)，dist[]就是從源到所有其他頂點(diǎn)之間的最短路徑長度。

算法步驟：

1）數(shù)據(jù)結(jié)構(gòu)。設(shè)置地圖的帶權(quán)鄰接矩陣為G.Edge[ ][ ],即如果從源點(diǎn)u 到頂點(diǎn) i 有邊，就令 G.Edge[ u ][ i ]等于<u,i>的權(quán)值，否則G.Edge[ u ][ i ] = 無窮大（寫程序時(shí)用一個(gè)大數(shù)表示例如Ox7fffffff）；采用一維數(shù)組dist[ i ]來記錄從源點(diǎn)到 i 頂點(diǎn)的最短路徑長度；采用一維數(shù)組p[ i ]來記錄最短路徑上 i 頂點(diǎn)的前驅(qū)。

2）初始化。令集合S = { u }，對(duì)于集合V-S中的所有頂點(diǎn)x,初始化 dist[ i ] = G.Edge[ u ][ i ]，如果源點(diǎn)u到頂點(diǎn)i有邊相連，初始化p[ i ] = u,否則p[ i ] = -1。

3) 找最小。在集合V-S中依照貪心策略來尋找時(shí)的dist[ j ]具有最小值的頂點(diǎn) t,即dist[ t ] = min(dist[j] | j屬于V-S集合)，則頂點(diǎn) t? 就是集合V-S中距離源點(diǎn)u 最近的頂點(diǎn)。

4）加入S戰(zhàn)隊(duì)。將頂點(diǎn) t 加入集合S中，同時(shí)更新V-S。

5）判結(jié)束。如何集合 V-S 為空，算法結(jié)束，否則轉(zhuǎn) 6）。

6） 借東風(fēng)。 在 3） 中已經(jīng)找到了源點(diǎn)到 t 的最短路徑，那么集合V-S 中所有與頂點(diǎn) t相鄰的頂點(diǎn) j,都可以借助 t 走捷徑。如果 dist[ j ] > dist[ t ]+G.Edge[t] [j],則dist[j] = dist[t] +G.Edge[t] [j] ,記錄頂點(diǎn)j 的前驅(qū)為t，有p[j] = t ,轉(zhuǎn) 3）。?

一個(gè)例子：

1）數(shù)據(jù)結(jié)構(gòu)

設(shè)置地圖的帶權(quán)鄰接矩陣為G.Edge[] []，即如果從頂點(diǎn)i 到頂點(diǎn) j 有邊，則G.Edge[ i ] [ j ]等于

< i, j >的權(quán)值，否則 G.Edge[ i ] [ j ] = 無窮大，如圖所示：

2) 初始化

令集合S = { 1 }, V-S = {2,3,4,5},對(duì)于集合V-S中的所有頂點(diǎn) x , 初始化最短距離數(shù)組 dist[ i ] = G.Edge[1][i],dist[ u ] = 0;如果源點(diǎn)1 到頂點(diǎn) i 有邊相連，初始化前驅(qū)數(shù)組 p[i] = 1,否則 p[i] = -1。

3） 找最小

在集合V-S = {2, 3, 4, 5}中，依照貪心策略來尋找 V-S 集合中dist[ ]最小的頂點(diǎn)t。

4）加入S戰(zhàn)隊(duì)

將頂點(diǎn) t? = 2加入集合S中S = {1,2},同時(shí)更新 V-S ={3 ,4 ,5 },如圖所示：

5）借東風(fēng)

剛剛找到了源點(diǎn)到 t = 2的最短路徑，那么對(duì)集合V-S中所有t 的鄰接點(diǎn) j,都可以借助t 走捷徑，我們從圖或鄰接矩陣都可以看出，2號(hào)結(jié)點(diǎn)的鄰接點(diǎn)是 3和 4 號(hào)結(jié)點(diǎn)。

6）找最小

在集合 V-S = { 3, 4, 5}中，依照貪心策略來尋找dist[ ]具有最小值的頂點(diǎn) t ，依照貪心策略來尋找 V-S 集合中 dist[ ]最小的頂點(diǎn)t：

7） 加入S戰(zhàn)隊(duì)

將頂點(diǎn)? t = 3加入集合S中 S = { 1, 2, 3},同時(shí)更新 V-S = {4, 5],如圖所示：

8） 借東風(fēng)

剛剛找到源點(diǎn)到 t = 3的最短路徑，那么對(duì)集合V-S中所有 t的鄰接點(diǎn)j,都可以借助 t 走捷徑。我們從圖中或者鄰接矩陣可以看出，3號(hào)結(jié)點(diǎn)的鄰接矩陣是4和5號(hào)結(jié)點(diǎn)。

先看4號(hào)結(jié)點(diǎn)能否借助3號(hào)走捷徑： dist[ 3 ] + G.Edge[3][4] = 4+7 = 11，而當(dāng)前 dist[ 4 ] = 8 < 11，比當(dāng)前路徑還長，因此不更新。

再看5號(hào)結(jié)點(diǎn)能否借助3號(hào)走捷徑：dist[3] + G.Edge[3][5] = 4+1 = 5,而當(dāng)前 dist[5] = 無窮大 > 5。因此可以走捷徑即 3 -> 5,更新 dist[5] 5,記錄頂點(diǎn) 5的前驅(qū)為 3，即p[5] = 3。

9）找最小

在集合 V-S = {4, 5}中，依照貪心策略來尋找V-S集合中dist[ ]最小的頂點(diǎn)t。

10） 加入S戰(zhàn)隊(duì)

將頂點(diǎn) t = 5 加入集合S中 S = {1, 2, 3, 5],同時(shí)更新V-S = { 4 },如圖所示：

11） 借東風(fēng)

剛剛找到了源點(diǎn)到 t = 5的最短路徑，那么集合 V-S 中所有t 的鄰接點(diǎn)j,都可以借助 t 走捷徑。我們從圖或鄰接矩陣可以看出，5號(hào)結(jié)點(diǎn)沒有鄰接點(diǎn)，因此不更新。

12） 找最小

在集合 V-S = { 4 }中，依照貪心策略來尋找 dist[ ]最小的頂點(diǎn) t，只有一個(gè)頂點(diǎn)，所以很容易找到，如圖所示：

13）加入S戰(zhàn)隊(duì)

將頂點(diǎn) t 加入集合S中，S = {1, 2, 3, 5, 4],同時(shí)更新V-S = { }。