《课程设计_最短路径算法.doc》由会员分享，可在线阅读，更多相关《课程设计_最短路径算法.doc（19页珍藏版）》请在金锄头文库上搜索。
1、沈阳航空航天大学 课课 程程 设设 计计 报报 告告 课程设计名称：数据结构课程设计数据结构课程设计 课程设计题目：最短路径算法最短路径算法 院（系）：计算机学院 专 业：计算机科学与技术 班 级： 学 号：33 姓 名： 指导教师： 目目 录录 1 1 课程设计介绍课程设计介绍.1 1.1 课程设计内容1 1.2 课程设计要求1 2 2 课程设计原理课程设计原理.2 2.1 课设题目粗略分析2 2.2 原理图介绍3 2.2.1 功能模块图3 2.2.2 流程图分析3 3 数据结构分析数据结构分析.8 3.1 存储结构.8 3.2 算法描述8 4 4 调试与分析调试与分析.9 4.1 调试过程
2、9 4.2 程序执行过程9 参考文献参考文献.11 附附 录（关键部分程序清单）录（关键部分程序清单）.12 0 1 1 课程设计介绍课程设计介绍 1.11.1 课程设计内容课程设计内容 设计程序，实现最短路径的求法，系统主要功能如下： 1. 编写算法能够建立带权图，并能够用 Dijkstra 算法求该图的最短路径。 2. 能够选择图上的任意一顶点做为开始节点。最短路径输出不必采用图 形方式，可顶点序列方式输出。 1.21.2 课程设计要求课程设计要求 1.带权图的顶点信息用字符串，数据可自定。 2.参考相应的资料，独立完成课程设计任务。 3.较规范课程设计报告和软件代码。 沈阳航空航天大学课
3、程设计报告 1 2 2 课程设计原理课程设计原理 2.12.1 课设题目粗略分析课设题目粗略分析 根据课设题目要求，拟将整体程序分为三大模块。两个子模块相互独立，没 有嵌套调用的情况，在主模块中调用上面两个子模块以下是三个模块的大体分析： 1.建立有向图的存储结构. 2.应用 Dijkstra 算法求出该有向图的最短路径。 3.在主函数中调用上面两个子函数，完成求最短路径的程序设计。 4. 2 2.22.2 原理图介绍原理图介绍 2.2.1 功能模块图功能模块图 求最短路径求最短路径 main 函数函数 Create 函数函数 Dijkstra 函数函数 图 2.1 功能模块图 2.2.2 流
4、程图分析流程图分析 1.主函数 2.2 主函数流程图 2.Create 函数 开始开始 输入数据输入数据 调用调用 Create 函数函数 调用调用 Dijkstra 函数函数 沈阳航空航天大学课程设计报告 3 开始开始 i=1 ivexsi=i i=i+1 Y N i=1 i=n j=1 jarcsij=Maxint N Y N Y j=j+1 k=1 4 karcsij=w k=k+1 结束 Y N 2.3Create 函数流程图 3.Dijkstra 函数 开始开始 int D2MVnum,P2MVnum v=1 v=n Sv=FALSE,D2v=Garcsv1v P2v=v1if(D2
5、vMaxint) P2v=0 v=v+1 Y N 沈阳航空航天大学课程设计报告 5 D2v1=0,Sv1=TRUE i=2 i=n N Y v=w,min=D2w if(!Sw Adjmatrix arcsMVNumMVNum； Mgraph; 3.23.2 算法描述算法描述 1. Dijkstra 算法核心是贪心，实质是按路径长度递增产生诸顶点的最短路径 算法。 迪杰斯特拉算法可用自然语言描述如下： 初始化 S 和 D,置空最短路径终点集，置初始的最短路径值； Sv1=TRUE;Dv1=0; While(S 集中的顶点数n) 开始循环，每次求的 v1 到某个 v 顶点的最短路径，并将 v 加
6、到 S 集中; Sv=TRUE; 更新当前最短路径及距离。 2Dijkstra 算法结束后，通过设置一个数组记录下一个节点的前趋节点，然后 通过倒叙的方式输出该最短路径。 8 4 4 调试与分析调试与分析 4.14.1 调试过程调试过程 在调试程序是主要遇到一下几类问题： 1. 程序完成后，调试时没有发现问题，但是当输入开始节点后，运行框却不停 的出现”-a”,后来重新检查程序时发现 for 循环的括号后面多了一个”;”，去掉 该分号之后，程序可以运行。 2. 程序可以运行，但是输出结果不是有序的，解决方法，设立一个前驱数组， 用以记录节点的双亲节点，然后按照倒叙的方式读出该条最短路径的有向序
7、 列。 4.2 程序执行过程程序执行过程 4.1 程序执行过程 沈阳航空航天大学课程设计报告 9 4.2 程序执行过程 10 参考文献参考文献 1 数据结构 （用面向对象方法与 C+描述） ，殷人昆等，清华大学出版社， 2010 年 3 月。 2 算法与数据结构习题精解和实验指导 ，宁正元等，清华大学出版社， 2009 年 6 月。 3 数据结构课程设计 ，苏仕华等，机械工业出版社，2010 年 3 月。 4C 程序设计 ，谭浩强编，清华大学出版社，2006 年 6 月。 沈阳航空航天大学课程设计报告 11 附附 录（关键部分程序清单）录（关键部分程序清单） 程序代码程序代码 #include
8、 #include #define MVNum 100 #define Maxint 32767 typedef char 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
9、,w; char a,b; for(i=1;ivexsi=i; for(i=1;i=n;i+) for(j=1;jarcsij=Maxint; printf(“输入%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; 12 boolean SMVNum; for(v=1;v=n;v+) Sv=FALSE; D2v=G.arcsv1v; if(D2vMaxint) P2v=
10、v1; else P2v=0; D2v1=0;Sv1=TRUE; for(i=2;i=n;i+) min=Maxint; for(w=1;w=n;w+) if(!Swmin=D2w; Sv=TRUE; for(w=1;w=n;w+) if(!Sw 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; 沈阳航空航天大学课程设计
11、报告 13 int n,e,v; char ch; printf(“输入图中顶点个数和边数 n,e:“); scanf(“%d,%d“, CreateMGraph( while(1) printf(“求最短路径，输入开始点 v:“); fflush(stdin); scanf(“%c“, v=ch-a+1; Dijkstra(G,v,n); 14 课程设计总结：课程设计总结： 本次课程设计涉及到的范围很广，让我能够比较系统的对 C 语言和数据结 构进行一次整理和复习。同时有了很多的体会和经验。 1. 又一次复习了 C 语言，在这次课程设计中我体会到 C 语言超强的逻辑性， 能够熟练使用 VC+
12、的编译环境，也对这两门课程有了新的认识，他们既有联系， 又相互区别，在编写程序过程中要灵活应用。 2. 对数据结构的理解有待加强，这次课程设计应用的算法是 Dijkstra 算 法。在学习的过程中自己就对这方面的知识比较生疏，所以刚拿到这个课设题 目时，自己还是有些不自信，好在自己没有气馁，一步一步的努力终于取得了 成功。 3. 此次设计让我意识到程序设计要求我们必须有不放弃的精神，不能因为 几个错误就轻言放弃，只有坚持不懈方能取得成功。 4. 此次课程设计时间虽短，但我所收获的是永恒的。它让我尝到了学习的 快乐，成功的喜悦，更让我懂得了不少做人的道理。要完成一项任务或把东西 学好就必须有足够的信心，持久的耐心，有面对困难无所畏惧的精神，这对我 日后的学习和生活产生了深远一个影响。 指导教师评语： 指导教师(签字)： 年 月 日 课程设计成绩
