课程设计-最短路径算法

沈阳大学课程设计报告课程设计名称：数据结构课程设计课程设计题目：最短路径算法院（系）：信息工程学院专业：通信工程专业班级：12级通信2班学号：F1258212姓名：刘维成指导教师：沈阳航空航天大学课程设计报告I目录1课程设计介绍............................................................................................................11.1课程设计内容.......................................................................................................11.2课程设计要求.......................................................................................................12课程设计原理............................................................................................................22.1课设题目粗略分析...............................................................................................22.2原理图介绍...........................................................................................................32.2.1功能模块图.....................................................................................................32.2.2流程图分析.....................................................................................................33数据结构分析............................................................................................................83.1存储结构................................................................................................................83.2算法描述...............................................................................................................84调试与分析................................................................................................................94.1调试过程...............................................................................................................94.2程序执行过程.........................................................................................................9参考文献.........................................................................................................................11附录（关键部分程序清单）..................................................................................12沈阳航空航天大学课程设计报告11课程设计介绍1.1课程设计内容设计程序，实现最短路径的求法，系统主要功能如下：1.编写算法能够建立带权图，并能够用Dijkstra算法求该图的最短路径。2.能够选择图上的任意一顶点做为开始节点。最短路径输出不必采用图形方式，可顶点序列方式输出。1.2课程设计要求1.带权图的顶点信息用字符串，数据可自定。2.参考相应的资料，独立完成课程设计任务。3.较规范课程设计报告和软件代码。沈阳航空航天大学课程设计报告错误!未指定书签。22课程设计原理2.1课设题目粗略分析根据课设题目要求，拟将整体程序分为三大模块。两个子模块相互独立，没有嵌套调用的情况，在主模块中调用上面两个子模块以下是三个模块的大体分析：1.建立有向图的存储结构.2.应用Dijkstra算法求出该有向图的最短路径。3.在主函数中调用上面两个子函数，完成求最短路径的程序设计。4.沈阳航空航天大学课程设计报告错误!未指定书签。32.2原理图介绍2.2.1功能模块图图2.1功能模块图2.2.2流程图分析1.主函数2.2主函数流程图2.Create函数求最短路径main函数Create函数Dijkstra函数开始输入数据调用Create函数调用Dijkstra函数沈阳航空航天大学课程设计报告错误!未指定书签。4开始i=1i=nG-vexs[i]=ii=i+1YNi=1i=nj=1j=ni=i+1G-arcs[i][j]=MaxintNYNYj=j+1k=1沈阳航空航天大学课程设计报告错误!未指定书签。53.Dijkstra函数k=nG-arcs[i][j]=wk=k+1结束YN2.3Create函数流程图开始intD2[MVnum],P2[MVnum]v=1v=nS[v]=FALSE,D2[v]=G..arcs[v1][v]P2[v]=v1if(D2[v]Maxint)P2[v]=0v=v+1YN沈阳航空航天大学课程设计报告错误!未指定书签。6D2[v1]=0,S[v1]=TRUEi=2i=nNYv=w,min=D2[w]if(!S[w]&&D2[w]min)S[v]=TRUEw=w+1w=1YNmin=Maxintw=1w=nw=nY沈阳航空航天大学课程设计报告错误!未指定书签。72.4Dijkstra函数流程图w=w+1i=i+1i=1输出数据i=i+1YD2[w]=D2[v]+G..arcs[if(!S[w]&&(D2[v]+G..av][w],P2[w]=vrcs[v][w]D2[w]))i=n结束N沈阳航空航天大学课程设计报告错误!未指定书签。83数据结构分析3.1存储结构一个图的邻接矩阵表示是唯一的。图的邻接矩阵表示，除了需要用一个二维数组存储顶点之间相邻关系的邻接矩阵外，通常还需要使用一个具有n个元素的一维数组存储顶点信息，其中下标为i的元素存储顶点vi的信息。因此，图的邻接矩阵的存储结构定义如下:#defineMVNum50typedefstruct{VertexTypevexs[MVNum];Adjmatrixarcs[MVNum][MVNum]；}Mgraph;3.2算法描述1.Dijkstra算法核心是贪心，实质是按路径长度递增产生诸顶点的最短路径算法。迪杰斯特拉算法可用自然语言描述如下：初始化S和D,置空最短路径终点集，置初始的最短路径值；S[v1]=TRUE;D[v1]=0;While(S集中的顶点数n){开始循环，每次求的v1到某个v顶点的最短路径，并将v加到S集中;S[v]=TRUE;更新当前最短路径及距离。}2Dijkstra算法结束后，通过设置一个数组记录下一个节点的前趋节点，然后通过倒叙的方式输出该最短路径。沈阳航空航天大学课程设计报告错误!未指定书签。94调试与分析4.1调试过程在调试程序是主要遇到一下几类问题：1.程序完成后，调试时没有发现问题，但是当输入开始节点后，运行框却不停的出现”-a”,后来重新检查程序时发现for循环的括号后面多了一个”;”，去掉该分号之后，程序可以运行。2.程序可以运行，但是输出结果不是有序的，解决方法，设立一个前驱数组，用以记录节点的双亲节点，然后按照倒叙的方式读出该条最短路径的有向序列。4.2程序执行过程4.1程序执行过程沈阳航空航天大学课程设计报告错误!未指定书签。104.2程序执行过程沈阳航空航天大学课程设计报告错误!未指定书签。11参考文献[1]《数据结构》（用面向对象方法与C++描述），殷人昆等，清华大学出版社，2010年3月。[2]《算法与数据结构习题精解和实验指导》，宁正元等，清华大学出版社，2009年6月。[3]《数据结构课程设计》，苏仕华等，机械工业出版社，2010年3月。[4]《C程序设计》，谭浩强编，清华大学出版社，2006年6月。沈阳航空航天大学课程设计报告错误!未指定书签。12附录（关键部分程序清单）程序代码#includestdio.h#includestdlib.h#defineMVNum100#defineMaxint32767typedefcharVertexType;typedefintAdjmatrix;typedefenum{FALSE,TRUE}boolean;typedefstruct{VertexTypevexs[MVNum];Adjmatrixarcs[MVNum][MVNum];}MGraph;intD1[MVNum],P1[MVNum];intD[MVNum][MVNum],P[MVNum][MVNum];voidCreateMGraph(MGraph*G,intn,inte){inti,j,k,w;chara,b;for(i=1;i=n;i++)G-vexs[i]=i;for(i=1;i=n;i++)for(j=1;j=n;j++)G-arcs[i][j]=Maxint;printf(输入%d条边的i,j及w:\n,e);for(k=1;k=e;k++){fflush(stdin);scanf(%c,%c,%d,&a,&b,&w);i=a-'a'+1;j=b-'a'+1;G-arcs[i][j]=w;}printf(有向图的存储结构建立完毕!\n);}voidDijkstra(MGraphG,intv1,intn){intD2[MVNum],P2[MVNum];intv,i,w,min;沈阳航空航天大学课程设计报告错误!未指定书签。13booleanS[MVNum];for(v=1;v=n;v++){S[v]=FALSE;D2[v]=G.arcs[v1][v];if(D2[v]Maxint)P2[v]=v1;elseP2[v]=0;}D2[v1]=0;S[v1]=TRUE;for(i=2;i=n;i++){min=Maxint;for(w=1;w=n;w++)if(!S[w]&&D2[w]min){v=w;min=D2[w];}S[v]=TRUE;for(w=1;w=n;w++)if(!S[w]&&(D2[v]+G.arcs[v][w]D2[w])){D2[w]=D2[v]+G.arcs[v][w];P2[w]=v;}}printf(路径长度路径\n);for(i=1;i=n;i++){printf(%5d,D2[i]);pr