迪杰斯特拉算法和floyd算法实现无向图的最短路径的计算和求解

《迪杰斯特拉算法和floyd算法实现无向图的最短路径的计算和求解》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、12沈阳理工大学算法与创新设计课程设计摘要本次课程设计主要核心为利用迪杰斯特拉算法和Floyd算法实现无向图的最短路径的计算和求解。要求理解算法的具体实现流程、学会正确使用该算法求解实际问题。本次课程设计具体内容是：通过对两个算法的理解与应用来比较两个算法的优缺点。本程序要求结合最短路算法以及相应的数据结构的定义和使用，实现一个最短路径算法的简单应用。本课程设计是对书本知识的简单应用，以此培养大家用书本知识解决实际问题的能力；培养实际工作所需要的动手能力；培养以科学理论和工程上能力的技术，规范地开发大型、复杂、高质量的应用软件和系统软件。

2、关键字：迪杰斯特拉算法，Floyd算法，最短路径，算法设计，数据结构1212沈阳理工大学算法与创新设计课程设计目录摘要1一、Dijkstra算法31.1定义概览31.2算法描述31.2.1算法思想：31.1.2算法步骤41.3算法代码实现51.4算法实例6二、Floyd算法82.1定义概览82.2算法描述82.2.1算法思想原理82.3算法代码实现11三、结论12四、参考文献131212沈阳理工大学算法与创新设计课程设计一、Dijkstra算法1.1定义概览Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他

3、所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权边。问题描述：在无向图G=(V,E)中，假设每条边E[i]的长度为w[i]，找到由顶点V0到其余各点的最短路径。 1.2算法描述1.2.1算法思想：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径,就将加入到集合S

4、中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。1.1.2算法步骤：a.初始时，S只包含源点，即S＝{v}，v的距离为0。U包含除v外的其他顶点，即:U={其余顶点}，若v与U中顶点u有边，

5、则正常有权值，若u不是v的出边邻接点，则权值为∞。1212沈阳理工大学算法与创新设计课程设计b.从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。c.以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。d.重复步骤b和c直到所有顶点都包含在S中。 执行动画过程如下图1.3算法代码实现：constintMAXINT=32767;constintMAXNUM=1

6、0;intdist[MAXNUM];intprev[MAXNUM]; intA[MAXUNM][MAXNUM]; voidDijkstra(intv0) { boolS[MAXNUM];//判断是否已存入该点到S集合中 intn=MAXNUM; for(inti=1;i<=n;++i){ dist[i]=A[v0][i]; S[i]=false;//初始都未用过该点 if(dist[i]==MAXINT) prev[i]=-1; else 1212沈阳理工大学算法与创新设计课程设计prev[i]=v0; } dist[v0]=0; 　S[

7、v0]=true;　　 　for(inti=2;i<=n;i++) 　　{ intmindist=MAXINT; intu=v0;　　//找出当前未使用的点j的dist[j]最小值 for(intj=1;j<=n;++j) if((!S[j])&&dist[j]

8、[j])//在通过新加入的u点路径找到离v0点更短的路径　　{ dist[j]=dist[u]+A[u][j];//更新dist prev[j]=u;//记录前驱顶点　　} 　　} 　　} }