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

尚寶欣,陳 卓（東北電力大學(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í)時，往往會強(qiáng)調(diào)兩者的不同點(diǎn)，卻忽略了兩者的相似性。本文分析兩個算法的相同點(diǎn)，使用C語言編寫兩種算法的通用程序。

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

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

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

1 Prim算法與Dijkstra算法分析

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

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

2 代碼實(shí)現(xiàn)

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

表1 主要函數(shù)

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

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

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

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

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;

// 找滿足最小距離條件的頂點(diǎn)

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算法的相同點(diǎn)，用Visual C++ 6.0編程，實(shí)現(xiàn)二者的共用程序，這便于學(xué)生對兩種算法的理解。通過比較二者的異同，使學(xué)生能熟練掌握運(yùn)用兩種方法，也提升學(xué)生的獨(dú)立思考能力。

參考文獻(xiàn):

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

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

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