摘 要：數(shù)據(jù)結(jié)構(gòu)中，普里姆算法與迪杰斯特拉算法分析考慮的均是帶權(quán)圖的造價最小問題，而這兩種方法在生活的諸多領(lǐng)域應(yīng)用相當廣泛，但是學生往往把這兩種算法混為一談，似乎認為這兩種算法求得的結(jié)果是一樣的，而不明白為什么一個稱為最小生成樹，另一個則是最短路徑。本文從算法的思想入手，通過示意圖進行對比分析，突出不同點，使學生在今后的學習中加深對知識點的理解與認識。

關(guān)鍵詞：普里姆；迪杰斯特拉；示意圖

中圖分類號：TP301.6

1 Prim算法與Dijstra算法思想分析比較

Prim算法是在由n 個頂點組成的無向連通圖中，取圖中任意一個頂點V作為生成樹的根，之后往生成樹上添加新的頂點W。在添加的頂點W和已經(jīng)在生成樹上的頂點V之間必定存在一條邊，并且該邊的權(quán)值在所有連通頂點V和W之間的邊中取值最小。之后繼續(xù)往生成樹上添加頂點，直至生成樹上含有n個頂點為止。一般情況下所添加的頂點應(yīng)滿足下列條件：在生成樹的構(gòu)造過程中，圖中n個頂點分屬兩個集合：已落在生成樹上的頂點集U和尚未落在生成樹上的頂點集V-U，則應(yīng)在所有連通U中頂點和V-U中頂點的邊中選取權(quán)值最小的邊。直到U中包含n個頂點，而V-U中為空集。

迪杰斯特拉（Dijkstra）算法是在由n個頂點組成的有向圖中，從指定一個頂點出發(fā)，提出按路徑長度的遞增次序，逐步產(chǎn)生最短路徑的算法，是單源點多目標點最短路徑。最短路徑的求解過程中，圖中的頂點也是分屬兩個集合：指定出發(fā)點的頂點為一個集合V，其余頂點為一個集合W。從W中選擇一個離V中頂點最近的一個頂點加入到V中，求出了長度最短的一條最短路徑，并把剛選擇加入最短路徑的頂點作為中間點，對其它頂點到源點的路徑長度進行修改，求出長度次短的一條最短路徑，依次類推，直到從頂點v到其它各頂點的最短路徑全部求出為止。

2 Prim算法與Dijstra算法處理步驟比較

Prim算法構(gòu)造最小生成樹的步驟是每次都從生成樹外頂點與生成樹內(nèi)頂點相連的邊中選擇代價最小的加入到生成樹，也就是每次按權(quán)值局部最小的方法，直到加入所有頂點和n-1條邊為止。對應(yīng)的步驟如下：

G=（V，E）是連通網(wǎng)，TE是G上最小生成樹中邊的集合。

初態(tài)：U={u0|u0∈V}，TE={}開始，重復(fù)執(zhí)行下述操作：

（1）在所有u∈U，v∈V-U的邊（u，v）∈E中找一條帶權(quán)最小的邊（u0，v0）并入集合TE，v0并入U。

（2）重復(fù)（1）直至U=V為止。此時TE中必有n-1條邊，則T=（V，TE）為N的最小生成樹。

迪杰斯特拉提出了一個按路徑長度遞增的次序產(chǎn)生最短路徑的算法。

首先，引進一個輔助向量D，它的每個分量D[i]表示當前找到的從始點v到每個終點vi的最短路徑的長度。它的初態(tài)為：若從v到vi有弧，則D[i]為弧上的權(quán)值；否則置D[i]為∞，顯然，長度為

D[j]=Min{D[i]|vi∈V}

的路徑就是從v出發(fā)的長度最短的一條最短路徑。此路徑為（v，vj）。那么，下一條長度次短的最短路徑的終點是vk，則可想而知，這條路徑或者是（v，vk），或者是（v，vj，vk）。它的長度或者是從v到vk的弧上的權(quán)值，或者是D[j]和從vj到vk的弧上的權(quán)值之和。具體步驟如下：

（1）S和T=V-S，S中存放已找到最短路徑的頂點，T存放當前還未找到最短路徑的頂點。初態(tài)，S中只包含源點v0

（2）不斷從T中選取到頂點v0路徑長度最短的頂點u加入到S中，S每加入一個新的頂點u，都要修改頂點v0到T中剩余頂點的最短路徑的長度，T中各頂點新的最短路徑長度值為原來的最短路徑長度值與頂點u的最短路徑長度值加上u到該頂點的路徑長度值中的較小值。

（3）重復(fù)（2），直到T的頂點全部加入到S中為止。

3 示意圖比較

由上圖圖1所示，用普里姆算法構(gòu)造最小生成樹，其過程如下表3.1.1～3.1.6：

4 Prim（普里姆）算法和Dijkstra（迪杰斯特拉）的區(qū)別

通過以上的分析我把這兩種算法的主要區(qū)別規(guī)納總結(jié)如下：

（1）分析對象不同，前者為無向圖，后者為有向圖。

（2）連通的頂點不同，前者連通所有頂點，且總的代價最低，后者為單源點多目標點最短路徑，所求得的是兩頂點之間代價最小。

（3）普里姆算法生成最小生成樹需重復(fù)n-1次，迪杰斯特拉算法則需重復(fù)n-2次。

5 總結(jié)

知識并不是孤立的，即存在著聯(lián)系又有區(qū)別，只有把相近的內(nèi)容加以對比分析，找出不同點，才能真正的理解和掌握所學的內(nèi)容，從而提高我們的學習效率。

參考文獻：

[1]楊劍.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學出版社，2011.

[2]嚴蔚敏.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學出版社，2006.