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

尚宝欣,陈 卓（东北电力大学 理学院,吉林 吉林 132012）

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

尚宝欣,陈 卓
（东北电力大学 理学院,吉林 吉林 132012）

摘 要：数据结构中，Prim算法与Dijkstra算法所求的均是赋权图的最小权值问题。Prim算法求连通赋权无向图的最小生成树，Dijkstra算法求赋权有向图的单源最短路径。在授课或是学习时，往往会强调两者的不同点，却忽略了两者的相似性。本文分析两个算法的相同点，使用C语言编写两种算法的通用程序。

关键词：Prim算法;Dijkstra算法;相似性;通用程序 Prim算法与Dijkstra算法简介

设有连通赋权无向图G，G中有n个顶点。Prim算法可描述为：任取G中一个顶点作为最小生成树的根，每次向当前树中添加一个顶点和一条边，要求这条边为当前所确定树的顶点与不在该树中顶点所连边中权值最小的一条边，重复n-1次，依次将无向图中所有顶点均添加至树中，最后得到最小生成树。

Dijkstra算法是在赋权有向图中，将源点做为最短路径的起始点，每次从最短路径以外的顶点集合中通过比较从源点经由最短路径中顶点到这些顶点路径权值的大小，选择权值最小的点加入最短路径集合，即找到了从源点到该点的最短路径，对余下的顶点进行类似的处理，重复次后，即求出单源到各顶点的最短路径。

1 Prim算法与Dijkstra算法分析

记所有顶点集合为V，Prim算法和Dijkstra算法均是将图中的顶点分为两部分，记所求的最小生成树或者单源最短路径的顶点集合为U，每次都在V-U集合中选择一个顶点放入U中，这个顶点的边要求满足算法所定义的距离极小性，依次选择，直到U=V时停止添加，所得到的树就能代表最小生成树或是单源最短路径。

两个算法的区别主要是对顶点之间距离的定义不同，Prim算法定义的距离是集合V-U中的点与U中点所确定边的最小权值，而Dijkstra算法定义的距离是源点到其他点的直接到达路径与通过中间点到达的路径的最小权值。

2 代码实现

根据上述分析，确定主体函数模块。Prim算法和Dijkstra算法除了距离定义不同以外，两者所求结果所表示的含义也不尽相同，因此最小生成树与单源最短路径的输出要分别用两个函数来完成。两者共用的调用函数根据主函数输入的信息确定距离函数与输出函数，此过程在该函数内部使用函数指针实现。表1列举出需要调用的主要函数。

表1 主要函数

两种算法的主要差别在于对顶点之间距离的定义不同。Prim算法中顶点u和v之间的距离为邻接矩阵ΑdjMat[u][v]中元素的值，由该矩阵可直接读出距离，在程序中用PrimDist表示；Dijkstra算法中顶点u和v的距离定义为从源点出发经由u点到达v点需要的最短距离，它需要判别有向图中距离是否存在，若存在则把邻接矩阵的权值加上上次循环得到的最短距离，即ΑdjMat[u][v] == -1 || lowcost[u] == -1 ? -1 : lowcost[u] + ΑdjMat[u][v]，在程序中用DijkDist表示。

PrimΑndDijk为两算法的共用函数。在该函数中使用函数指针实现不同距离函数及不同输出函数的选择。例如Prim算法时只需要输出最小生成树，包含顶点及边的权值即可；而Dijkstra算法则是输出源点到各个点的最短路径，因此需要输出完整的路径及最短的路径长度。使用PrintRes表示要输出程序的运行结果，则程序片断

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

表示algΤype为0时用Prim算法，非零时用Dijkstra算法。经过如此设定，函数运行过程中调用的距离与输出函数与所使用的算法能保持一致。共用函数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 结论

本文分析了Prim算法和Dijkstra算法的相同点，用Visual C++ 6.0编程，实现二者的共用程序，这便于学生对两种算法的理解。通过比较二者的异同，使学生能熟练掌握运用两种方法，也提升学生的独立思考能力。

参考文献:

[1]曲朝阳.数据结构[J].北京：中国电力出版社,2007．

[2]谭浩强.C语言程序设计教程[S].北京：高等教育出版社,2007．

作者简介：尚宝欣（1984-），硕士，讲师。