课程设计-最短路径算法

1、沈阳大学课程设计报告课程设计名称：数据结构课程设计课程设计题目：最短路径算法院（系）：信息工程学院专业：通信工程专业班 级：12级通信2班学 号：F1258212姓 名：刘维成指导教师：目 录 TOC o 1-5 h z HYPERLINK l bookmark10 o Current Document 1课程设计介绍1 HYPERLINK l bookmark13 o Current Document 1.1课程设计内容1 HYPERLINK l bookmark18 o Current Document 1.2课程设计要求1 HYPERLINK l bookmark24 o Current

2、 Document 2课程设计原理2 HYPERLINK l bookmark27 o Current Document 2.1课设题目粗略分析22.2原理图介绍32.2.1功能模块图3 HYPERLINK l bookmark41 o Current Document 2.2.2流程图分析33数据结构分析83.1存储结构8 HYPERLINK l bookmark72 o Current Document 3.2算法描述8 HYPERLINK l bookmark82 o Current Document 4调试与分析9 HYPERLINK l bookmark85 o Current Do

3、cument 4.1调试过程9 HYPERLINK l bookmark90 o Current Document 4.2程序执行过程9 HYPERLINK l bookmark93 o Current Document 参考文献11 HYPERLINK l bookmark100 o Current Document 附 录（关键部分程序清单） 121课程设计介绍1.1课程设计内容设计程序，实现最短路径的求法，系统主要功能如下：编写算法能够建立带权图，并能够用Dijkstra算法求该图的最短路径。能够选择图上的任意一顶点做为开始节点。最短路径输出不必采用图 形方式，可顶点序列方式输出。1.2

4、课程设计要求带权图的顶点信息用字符串，数据可自定。参考相应的资料，独立完成课程设计任务。较规范课程设计报告和软件代码。2课程设计原理2.1课设题目粗略分析根据课设题目要求，拟将整体程序分为三大模块。两个子模块相互独立，没 有嵌套调用的情况，在主模块中调用上面两个子模块以下是三个模块的大体分析:建立有向图的存储结构.应用Dijkstra算法求出该有向图的最短路径。在主函数中调用上面两个子函数，完成求最短路径的程序设计。4.2.2原理图介绍2.2.1功能模块图2.2.2流程图分析1.主函数图2.1功能模块图2.2主函数流程图2. Create 函数3.2.3Create函数流程图Dijkstra

5、函数i=12.4Dijkstra函数流程图3数据结构分析3.1存储结构一个图的邻接矩阵表示是唯一的。图的邻接矩阵表示，除了需要用一个二维数组 存储顶点之间相邻关系的邻接矩阵外，通常还需要使用一个具有n个元素的一维 数组存储顶点信息，其中下标为i的元素存储顶点vi的信息。因此，图的邻接矩 阵的存储结构定义如下：#define MVNum 50typedef struct VertexType vexsMVNum;Adjmatrix arcsMVNumMVNum；Mgraph;3.2算法描述Dijkstra算法核心是贪心，实质是按路径长度递增产生诸顶点的最短路径算 法。迪杰斯特拉算法可用自然语言描

6、述如下：初始化S和D,置空最短路径终点集，置初始的最短路径值；Sv1=TRUE;Dv1=0;While（S集中的顶点数n）开始循环，每次求的v1到某个v顶点的最短路径，并将v加到S集中; Sv=TRUE;更新当前最短路径及距离。2Dijkstra算法结束后，通过设置一个数组记录下一个节点的前趋节点，然后 通过倒叙的方式输出该最短路径。4调试与分析4.1调试过程在调试程序是主要遇到一下几类问题：程序完成后，调试时没有发现问题，但是当输入开始节点后，运行框却不停的 出现”-a”，后来重新检查程序时发现for循环的括号后面多了一个”二 去掉该 分号之后，程序可以运行。程序可以运行，但是输出结果不是有

7、序的，解决方法，设立一个前驱数组，用 以记录节点的双亲节点，然后按照倒叙的方式读出该条最短路径的有向序列。4.2程序执行过程4.1程序执行过程4.2程序执行过程参考文献数据结构（用面向对象方法与C+描述），殷人昆等，清华大学出版社， 2010年3月。算法与数据结构习题精解和实验指导，宁正元等，清华大学出版社， 2009年6月。数据结构课程设计，苏仕华等，机械工业出版社，2010年3月。C程序设计，谭浩强编，清华大学出版社，2006年6月。录（关键部分程序清单）程序代码#include#include#define MVNum 100#define Maxint 32767typedef cha

8、r VertexType;typedef int Adjmatrix;typedef enum FALSE,TRUEboolean;typedef struct VertexType vexsMVNum;Adjmatrix arcsMVNumMVNum;MGraph;int D1MVNum,P1MVNum;int DMVNumMVNum,PMVNumMVNum;void CreateMGraph(MGraph *G,int n,int e)int i,j,k,w;char a,b;for(i=1;ivexsi=i;for(i=1;i=n;i+)for(j=1;jarcsij=Maxint;pr

9、intf(输入d 条边的 i,j 及 w:n,e);for(k=1;karcsij=w;printf(有向图的存储结构建立完毕!n);void Dijkstra(MGraph G,int v1,int n)int D2MVNum,P2MVNum;int v,i,w,min;boolean SMVNum;for(v=1;v=n;v+)Sv=FALSE;D2v=G.arcsv1v;if(D2vMaxint)P2v=v1;elseP2v=0;D2v1=0;Sv1=TRUE;for(i=2;i=n;i+)min=Maxint;for(w=1;w=n;w+)if(!Sw&D2wmin)v=w;min=D

10、2w;Sv=TRUE;for(w=1;w=n;w+)if(!Sw&(D2v+G.arcsvwD2w)D2w=D2v+G.arcsvw;P2w=v;printf(路径长度路径n);for(i=1;i=n;i+)printf(%5d,D2i);printf(%5c,i-1+a);v=P2i;while(v!=0)printf(-%c,v-1+a);v=P2v;printf(n);void main()MGraph G;int n,e,v;char ch;printf(-输入图中顶点个数和边数n,e:);scanf(%d,%d”,&n,&e);CreateMGraph(&G,n,e);while(1

11、)printf(求最短路径，输入开始点v:);fflush(stdin);scanf(%c”,&ch);v=ch-a+1;Dijkstra(G,v,n);课程设计总结:本次课程设计涉及到的范围很广，让我能够比较系统的对C语言和数据结构 进行一次整理和复习。同时有了很多的体会和经验。又一次复习了 C语言，在这次课程设计中我体会到C语言超强的逻辑性， 能够熟练使用VC+的编译环境，也对这两门课程有了新的认识，他们既有联系， 又相互区别，在编写程序过程中要灵活应用。对数据结构的理解有待加强，这次课程设计应用的算法是Dijkstra算 法。在学习的过程中自己就对这方面的知识比较生疏，所以刚拿到这个课设题目 时，自己还是有些不自信，好在自己没有气馁，一步一步的努力终于取得了成功。此次设计让我意识到程序设计要求我们必须有不放弃的