Prim（普里姆）算法與Dijkstra（迪杰斯特拉）算法分析比較

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

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

中圖分類號(hào)：TP301.6

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

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

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

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

Prim算法構(gòu)造最小生成樹的步驟是每次都從生成樹外頂點(diǎn)與生成樹內(nèi)頂點(diǎn)相連的邊中選擇代價(jià)最小的加入到生成樹，也就是每次按權(quán)值局部最小的方法，直到加入所有頂點(diǎn)和n-1條邊為止。對(duì)應(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(xiǎn)。

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

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

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

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

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

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

（2）不斷從T中選取到頂點(diǎn)v0路徑長(zhǎng)度最短的頂點(diǎn)u加入到S中，S每加入一個(gè)新的頂點(diǎn)u，都要修改頂點(diǎn)v0到T中剩余頂點(diǎn)的最短路徑的長(zhǎng)度，T中各頂點(diǎn)新的最短路徑長(zhǎng)度值為原來(lái)的最短路徑長(zhǎng)度值與頂點(diǎn)u的最短路徑長(zhǎng)度值加上u到該頂點(diǎn)的路徑長(zhǎng)度值中的較小值。

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

3 示意圖比較

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

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

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

（1）分析對(duì)象不同，前者為無(wú)向圖，后者為有向圖。

（2）連通的頂點(diǎn)不同，前者連通所有頂點(diǎn)，且總的代價(jià)最低，后者為單源點(diǎn)多目標(biāo)點(diǎn)最短路徑，所求得的是兩頂點(diǎn)之間代價(jià)最小。

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

5 總結(jié)

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

參考文獻(xiàn)：

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

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