普里姆算法和迪克斯特拉算法的比較

對比是非常有效的學(xué)習(xí)方法。普里姆算法和迪克斯特拉算法是數(shù)據(jù)結(jié)構(gòu)中的典型算法，本文通過它們的設(shè)計(jì)和實(shí)現(xiàn)的對比，展示這種方法的意義。

1基本思想和數(shù)學(xué)描述比較

對一個連通網(wǎng)絡(luò)即無向加權(quán)連通圖，其權(quán)值總和最小的生成樹稱為最小生成樹。對一個有向網(wǎng)絡(luò)和一個稱為源點(diǎn)的頂點(diǎn)，求源點(diǎn)到其余各頂點(diǎn)的最短帶權(quán)路徑，稱為單源最短路徑。

普里姆(Prim)算法和迪克斯特拉(Dijkstra)算法分別是求最小生成樹和單源最短路徑的算法，它們的基本思想和數(shù)學(xué)描述對比見表1和表2。

2步驟和圖示比較

為了實(shí)現(xiàn)普里姆算法，首先引入一個結(jié)構(gòu)PathData來記錄候選邊信息，入選子網(wǎng)頂點(diǎn)作為始點(diǎn)，候選集頂點(diǎn)作為終點(diǎn)。其實(shí)無向網(wǎng)絡(luò)的邊是不分始點(diǎn)和終點(diǎn)的，這樣做僅是為了表述方便。

下面以圖1(b)為例，詳細(xì)介紹普里姆算法的實(shí)現(xiàn)步驟：

(1) 由始點(diǎn)0組成入選子網(wǎng)，其余頂點(diǎn)組成候選集。用無色環(huán)表示入選子網(wǎng)的頂點(diǎn)，有色環(huán)表示候選集頂點(diǎn)，虛線表示候選邊，權(quán)M代表一個很大的值(這個值應(yīng)該大于該網(wǎng)絡(luò)的所有權(quán)之和)，表示對應(yīng)的候選邊不存在(這樣做是為了計(jì)算方便)。把候選邊集存入PathData結(jié)構(gòu)數(shù)組。如圖1(c)所示。

(2) 在候選邊集中選定一條權(quán)最小的候選邊加到入選子網(wǎng)(用實(shí)線表示)?？焖賹?shí)現(xiàn)的方法是將候選邊集調(diào)整為小根堆，小根堆首元素就是最小的候選邊。如圖1(d)所示。

(3) 更新候選邊集(虛線)：如果最小候選邊存在，計(jì)算器加1，表示正式加到入選子網(wǎng)。然后，對新候選集的每一個頂點(diǎn)，它原來對應(yīng)的候選邊和入選集新的頂點(diǎn)與它的關(guān)聯(lián)邊比較，取小者，作為它對應(yīng)的新候選邊。例如，在圖1(e)中，原候選邊(0，1，60) 和新的關(guān)聯(lián)邊(2，1，50)比較，取小者(2，1，50)。

(4) 保存入選邊；對新候選邊集建堆，取最小的候選邊。實(shí)際的方法是，把存儲候選邊集的PathData結(jié)構(gòu)數(shù)組的首尾元素交換，數(shù)組元素個數(shù)減1，然后把該數(shù)組調(diào)整為堆。如圖1(f)所示。

(5) 重復(fù)(3)和(4)n-1次(這是最小生成樹的邊數(shù)ne)。如圖1(g)~1(l)所示。

(6) 如果計(jì)數(shù)器的值等于結(jié)點(diǎn)個數(shù)減1，函數(shù)返回值1，否則0。

為了實(shí)現(xiàn)迪克斯特拉算法，首先用結(jié)構(gòu)PathData來記錄候選路徑信息，包括路徑的始點(diǎn)，終點(diǎn)和帶權(quán)路徑長度。

下面以圖2(b)為例，詳細(xì)介紹迪克斯特拉算法的實(shí)現(xiàn)步驟：

(1) 由始點(diǎn)0組成入選子網(wǎng)，其余頂點(diǎn)組成候選集。用無色環(huán)表示入選子網(wǎng)的頂點(diǎn)，有色環(huán)表示候選集頂點(diǎn)，虛線表示候選路徑，M代表一個很大的值(這個值應(yīng)該大于該網(wǎng)絡(luò)所有帶權(quán)路徑長度之和)，表示對應(yīng)的候選路徑不存在(這樣做是為了計(jì)算方便)。把候選路徑集存入PathData結(jié)構(gòu)數(shù)組。如圖2(c)所示。

(2) 在候選路徑集中選定一條帶權(quán)路徑長度最短的加到入選子網(wǎng)(用實(shí)線表示)?？焖賹?shí)現(xiàn)的方法是將候選路徑集調(diào)整為小根堆，小根堆首元素就是帶權(quán)路徑長度最短的候選路徑。如圖2(d)所示。

(3) 更新候選路徑集(虛線)：如果最短候選路徑存在，計(jì)算器加1，表示正式加到入選子網(wǎng)。然后，對新候選集的每一個頂點(diǎn)，它原來對應(yīng)的候選路徑和以入選集新的頂點(diǎn)為前驅(qū)的特殊路徑比較，取小者，作為它對應(yīng)的新候選邊。例如，在圖2(e)中，原候選路徑<0，3> 和新的特殊路徑<0，1，3>比較，取小者<0，1，3>。

(4) 保存入選路徑；對新候選路徑集建堆，取最短的候選路徑。實(shí)際的方法是，把存儲候選路徑集的PathData結(jié)構(gòu)數(shù)組的首尾元素交換，數(shù)組元素個數(shù)減1，然后把該數(shù)組調(diào)整為堆。如圖2(f)所示。

(5) 重復(fù)(3)和(4)n-1次(這是最小生成樹的邊數(shù)ne)。如圖2(g)~2(l)所示。

如果計(jì)數(shù)器的值等于結(jié)點(diǎn)個數(shù)減1，函數(shù)返回值1，否則0。

struct PathData//用于最小生成樹算法的一種結(jié)點(diǎn)結(jié)構(gòu)

{

int start，dest;//邊的起點(diǎn)和終點(diǎn)的下標(biāo)

double cost;//邊上的權(quán)代表費(fèi)用

operator double(void)const{return(cost);}//成員轉(zhuǎn)換函數(shù)，用于比較運(yùn)算

};

為了完整地輸出每一條單源最短路徑和其帶權(quán)路徑長度，引入數(shù)組P(Path)和D(Distance)，P[i]的值表示序號為i的頂點(diǎn)所對應(yīng)的候選路徑的終點(diǎn)前驅(qū)的序號(如果沒有前驅(qū)，值為-1)，D[i]的值表示序號為i的頂點(diǎn)所對應(yīng)的候選路徑的帶權(quán)長度。

不難看出，迪克斯特拉算法與普里姆算法有許多相似之處，這從它們的基本思想描述和過程示意圖可以看出來，表1又以對比的方式給出了迪克斯特拉算法的實(shí)現(xiàn)代碼，目的是倡導(dǎo)這種比較的學(xué)習(xí)方法。

3代碼比較

普里姆算法和迪克斯特拉算法的代碼比較見表3，其中陰影部分是不同之處。

為了完整地輸出每一條單源最短路徑和其帶權(quán)路徑長度，引入數(shù)組P(Path)和D，P[i]的值表示序號為i的頂點(diǎn)所對應(yīng)的候選路徑的終點(diǎn)前驅(qū)的序號(如果沒有前驅(qū)，值為-1)，D[i]的值表示序號為i的頂點(diǎn)所對應(yīng)的候選路徑的帶權(quán)長度。

4小結(jié)

課程改革首先是課程內(nèi)容的改革，而內(nèi)容的改革必然反映在形式的變化上。對比的形式是我們課程改革教材中的主要形式，這種形式有助于理解C++龐雜的概念，把握數(shù)據(jù)結(jié)構(gòu)抽象的算法。