翻新时间:2023-05-17
Prim算法与Dijkstra算法相似性有多少
摘 要:数据结构中,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列举出需要调用的主要函数。
两种算法的主要差别在于对顶点之间距离的定义不同。Prim算法中顶点u和v之间的距离为邻接矩阵AdjMat[u][v]中元素的值,由该矩阵可直接读出距离,在程序中用PrimDist表示;Dijkstra算法中顶点u和v的距离定义为从源点出发经由u点到达v点需要的最短距离,它需要判别有向图中距离是否存在,若存在则把邻接矩阵的权值加上上次循环得到的最短距离,即AdjMat[u][v] == -1 || lowcost[u] == -1 ? -1 : lowcost[u] + AdjMat[u][v],在程序中用DijkDist表示。
PrimAndDijk为两算法的共用函数。在该函数中使用函数指针实现不同距离函数及不同输出函数的选择。例如Prim算法时只需要输出最小生成树,包含顶点及边的权值即可;而Dijkstra算法则是输出源点到各个点的最短路径,因此需要输出完整的路径及最短的路径长度。使用PrintRes表示要输出程序的运行结果,则程序片断
algType? (PrintRes = DijkPrint,Distance = DijkDist ):(PrintRes = PrimPrint, Distance = PrimDist);
表示algType为0时用Prim算法,非零时用Dijkstra算法。经过如此设定,函数运行过程中调用的距离与输出函数与所使用的算法能保持一致。共用函数PrimAndDijk的详细源代码如下:
void PrimAndDijk(int** AdjMat, int vexCnt, int src, int algType=0){
int* closest = NULL; int* lowcost = NULL;
int* flag = NULL;
int(*Distance)(int** AdjMat, 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];
// algType为0时用Prim算法,非零时用Dijkstra算法
algType? (PrintRes=DijkPrint, Distance=DijkDist) : (PrintRes =PrimPrint, Distance = PrimDist);
for (i = 0; i < vexCnt; i++){// 初始化过程
flag[i] = 0; lowcost[i] = AdjMat[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(AdjMat, 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编程,实现二者的共用程序,这便于学生对两种算法的理解。通过比较二者的异同,使学生能熟练掌握运用两种方法,也提升学生的独立思考能力。
下载文档
网友最新关注
- 落叶旅行记
- 邻里情
- 擦干泪,我对自己说
- 闲不着的奶奶
- 饮料风波
- 我的妈妈
- 母亲的故事
- 为爷爷敲背
- 狂欢夜
- 爷爷,我想对您说
- 游劳动公园
- 小鸭成长日记
- 我的爸爸
- 乌鸦喝水后后传
- 可爱的小白
- 承租房屋、门面业主治安责任书
- 最新幼儿园安全责任书
- 消毒岗位职责和任务
- 口腔科护士职责和任务
- 幼儿园教师安全责任书
- 学校安全管理责任书
- 财务部经理岗位经济责任书
- 教导主任岗位安全责任书
- 中学家长安全责任书
- 学校学生安全责任书
- 幼儿园交通安全责任书
- 教师安全值班责任书
- 校车司机责任书
- 幼儿园门卫安全责任书
- 用车人员责任书
- 浅论解读TCL集团体育营销战略
- 混合型塑胶跑道、塑胶球场施工方案
- 零售业客户忠诚度与营销策略分析
- 试论我国国家赔偿法的特色_法学理论论文(1)
- 宜居城市的小区绿化
- 商业生态系统、公司治理功能延伸及重新建构
- 浅论“法治”与“法律权威”_法学理论论文(1)
- 浅析当前医药企业市场营销中的问题与对策
- 园林规划设计的步骤
- 园林植物在人类生活中的作用
- 移动营销:基于短信息服务的消费者接受实证研究
- 诚信原则是保险业的立业之本_法学理论论文(1)
- 试论网上音乐品牌营销战略分析
- 从六度分离理论看网络深度营销价值
- 论物业管理中的法律问题_法学理论论文(1)
- 《呼风唤雨的世纪》第一课时说课设计
- 《呼风唤雨的世纪》教学设计7
- 《呼风唤雨的世纪》教学设计3
- 《呼风唤雨的世纪》教学目标和教材简说
- 《呼风唤雨的世纪》词句解析
- 《呼风唤雨的世纪》第一课时教学设计2
- 《呼风唤雨的世纪》第一课时教学设计3
- 《呼风唤雨的世纪》教学建议
- 《呼风唤雨的世纪》快乐练习:课堂达标(二)
- 《呼风唤雨的世纪》第一课时教学设计
- 《呼风唤雨的世纪》教学设计2
- 《呼风唤雨的世纪》词语
- 《尺有所短 寸有所长》快乐练习:课堂达标(二)
- 《呼风唤雨的世纪》教学设计1第一课时
- 《呼风唤雨的世纪》教学设计1第二课时