尚寶欣,陳 卓（東北電力大學(xué) 理學(xué)院,吉林 吉林 132012）

Prim算法與Dijkstra算法相似性有多少

尚寶欣,陳 卓
（東北電力大學(xué) 理學(xué)院,吉林 吉林 132012）

摘 要：數(shù)據(jù)結(jié)構(gòu)中，Prim算法與Dijkstra算法所求的均是賦權(quán)圖的最小權(quán)值問題。Prim算法求連通賦權(quán)無向圖的最小生成樹，Dijkstra算法求賦權(quán)有向圖的單源最短路徑。在授課或是學(xué)習(xí)時，往往會強調(diào)兩者的不同點，卻忽略了兩者的相似性。本文分析兩個算法的相同點，使用C語言編寫兩種算法的通用程序。

關(guān)鍵詞：Prim算法;Dijkstra算法;相似性;通用程序 Prim算法與Dijkstra算法簡介

設(shè)有連通賦權(quán)無向圖G，G中有n個頂點。Prim算法可描述為：任取G中一個頂點作為最小生成樹的根，每次向當(dāng)前樹中添加一個頂點和一條邊，要求這條邊為當(dāng)前所確定樹的頂點與不在該樹中頂點所連邊中權(quán)值最小的一條邊，重復(fù)n-1次，依次將無向圖中所有頂點均添加至樹中，最后得到最小生成樹。

Dijkstra算法是在賦權(quán)有向圖中，將源點做為最短路徑的起始點，每次從最短路徑以外的頂點集合中通過比較從源點經(jīng)由最短路徑中頂點到這些頂點路徑權(quán)值的大小，選擇權(quán)值最小的點加入最短路徑集合，即找到了從源點到該點的最短路徑，對余下的頂點進行類似的處理，重復(fù)次后，即求出單源到各頂點的最短路徑。

1 Prim算法與Dijkstra算法分析

記所有頂點集合為V，Prim算法和Dijkstra算法均是將圖中的頂點分為兩部分，記所求的最小生成樹或者單源最短路徑的頂點集合為U，每次都在V-U集合中選擇一個頂點放入U中，這個頂點的邊要求滿足算法所定義的距離極小性，依次選擇，直到U=V時停止添加，所得到的樹就能代表最小生成樹或是單源最短路徑。

兩個算法的區(qū)別主要是對頂點之間距離的定義不同，Prim算法定義的距離是集合V-U中的點與U中點所確定邊的最小權(quán)值，而Dijkstra算法定義的距離是源點到其他點的直接到達路徑與通過中間點到達的路徑的最小權(quán)值。

2 代碼實現(xiàn)

根據(jù)上述分析，確定主體函數(shù)模塊。Prim算法和Dijkstra算法除了距離定義不同以外，兩者所求結(jié)果所表示的含義也不盡相同，因此最小生成樹與單源最短路徑的輸出要分別用兩個函數(shù)來完成。兩者共用的調(diào)用函數(shù)根據(jù)主函數(shù)輸入的信息確定距離函數(shù)與輸出函數(shù)，此過程在該函數(shù)內(nèi)部使用函數(shù)指針實現(xiàn)。表1列舉出需要調(diào)用的主要函數(shù)。

表1 主要函數(shù)

兩種算法的主要差別在于對頂點之間距離的定義不同。Prim算法中頂點u和v之間的距離為鄰接矩陣ΑdjMat[u][v]中元素的值，由該矩陣可直接讀出距離，在程序中用PrimDist表示；Dijkstra算法中頂點u和v的距離定義為從源點出發(fā)經(jīng)由u點到達v點需要的最短距離，它需要判別有向圖中距離是否存在，若存在則把鄰接矩陣的權(quán)值加上上次循環(huán)得到的最短距離，即ΑdjMat[u][v] == -1 || lowcost[u] == -1 ? -1 : lowcost[u] + ΑdjMat[u][v]，在程序中用DijkDist表示。

PrimΑndDijk為兩算法的共用函數(shù)。在該函數(shù)中使用函數(shù)指針實現(xiàn)不同距離函數(shù)及不同輸出函數(shù)的選擇。例如Prim算法時只需要輸出最小生成樹，包含頂點及邊的權(quán)值即可；而Dijkstra算法則是輸出源點到各個點的最短路徑，因此需要輸出完整的路徑及最短的路徑長度。使用PrintRes表示要輸出程序的運行結(jié)果，則程序片斷

algΤype? (PrintRes = DijkPrint,Distance = DijkDist ):(PrintRes = PrimPrint, Distance = PrimDist);

表示algΤype為0時用Prim算法，非零時用Dijkstra算法。經(jīng)過如此設(shè)定，函數(shù)運行過程中調(diào)用的距離與輸出函數(shù)與所使用的算法能保持一致。共用函數(shù)PrimΑndDijk的詳細源代碼如下：

void PrimΑndDijk(int** ΑdjMat, int vexCnt, int src, int algΤype=0){

int* closest = NULL; int* lowcost = NULL;

int* flag = NULL;

int(*Distance)(int** ΑdjMat, int u, int v, int* lowcost);

void(*PrintRes)(int* lowcost, int* closest, int n, int v);

int i, j, min, k, d;

closest = new int[vexCnt]; lowcost = new int[vexCnt];

flag = new int[vexCnt];

// algΤype為0時用Prim算法，非零時用Dijkstra算法

algΤype? (PrintRes=DijkPrint, Distance=DijkDist) : (PrintRes =PrimPrint, Distance = PrimDist);

for (i = 0; i ＜ vexCnt; i++){// 初始化過程

flag[i] = 0; lowcost[i] = ΑdjMat[src][i]; closest[i] = src;}

flag[src] = 1;

// 找滿足最小距離條件的頂點

for (i = 1; i ＜ vexCnt; i++){

min = 300000; k = -1;

for (j = 0; j ＜ vexCnt; j++){

if (flag[j]!=1 && lowcost[j] != -1 && lowcost[j] !=0 && lowcost[j] ＜min)

{min = lowcost[j]; k = j;}

}

flag[k] = 1;

for (j = 0; j ＜ vexCnt; j++){

d = -1;

if (!flag[j]){

d = Distance(ΑdjMat, k, j, lowcost);

if (d!=-1 && d!=0 && (lowcost[j]＞d || lowcost[j]==-1)){ lowcost[j] = d;

closest[j] = k; }}}}

PrintRes(lowcost, closest, vexCnt, src);

delete[] closest; delete[] lowcost; delete[] flag;

}

3 結(jié)論

本文分析了Prim算法和Dijkstra算法的相同點，用Visual C++ 6.0編程，實現(xiàn)二者的共用程序，這便于學(xué)生對兩種算法的理解。通過比較二者的異同，使學(xué)生能熟練掌握運用兩種方法，也提升學(xué)生的獨立思考能力。

參考文獻:

[1]曲朝陽.數(shù)據(jù)結(jié)構(gòu)[J].北京：中國電力出版社,2007．

[2]譚浩強.C語言程序設(shè)計教程[S].北京：高等教育出版社,2007．

作者簡介：尚寶欣（1984-），碩士，講師。