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

對比是非常有效的學習方法。普里姆算法和迪克斯特拉算法是數據結構中的典型算法，本文通過它們的設計和實現的對比，展示這種方法的意義。

1基本思想和數學描述比較

對一個連通網絡即無向加權連通圖，其權值總和最小的生成樹稱為最小生成樹。對一個有向網絡和一個稱為源點的頂點，求源點到其余各頂點的最短帶權路徑，稱為單源最短路徑。

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

2步驟和圖示比較

為了實現普里姆算法，首先引入一個結構PathData來記錄候選邊信息，入選子網頂點作為始點，候選集頂點作為終點。其實無向網絡的邊是不分始點和終點的，這樣做僅是為了表述方便。

下面以圖1(b)為例，詳細介紹普里姆算法的實現步驟：

(1) 由始點0組成入選子網，其余頂點組成候選集。用無色環表示入選子網的頂點，有色環表示候選集頂點，虛線表示候選邊，權M代表一個很大的值(這個值應該大于該網絡的所有權之和)，表示對應的候選邊不存在(這樣做是為了計算方便)。把候選邊集存入PathData結構數組。如圖1(c)所示。

(2) 在候選邊集中選定一條權最小的候選邊加到入選子網(用實線表示)。快速實現的方法是將候選邊集調整為小根堆，小根堆首元素就是最小的候選邊。如圖1(d)所示。

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

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

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

(6) 如果計數器的值等于結點個數減1，函數返回值1，否則0。

為了實現迪克斯特拉算法，首先用結構PathData來記錄候選路徑信息，包括路徑的始點，終點和帶權路徑長度。

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

(1) 由始點0組成入選子網，其余頂點組成候選集。用無色環表示入選子網的頂點，有色環表示候選集頂點，虛線表示候選路徑，M代表一個很大的值(這個值應該大于該網絡所有帶權路徑長度之和)，表示對應的候選路徑不存在(這樣做是為了計算方便)。把候選路徑集存入PathData結構數組。如圖2(c)所示。

(2) 在候選路徑集中選定一條帶權路徑長度最短的加到入選子網(用實線表示)。快速實現的方法是將候選路徑集調整為小根堆，小根堆首元素就是帶權路徑長度最短的候選路徑。如圖2(d)所示。

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

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

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

如果計數器的值等于結點個數減1，函數返回值1，否則0。

struct PathData//用于最小生成樹算法的一種結點結構

{

int start，dest;//邊的起點和終點的下標

double cost;//邊上的權代表費用

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

};

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

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

3代碼比較

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

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

4小結

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