数据结构课程设计报告--Dijkstra算法求最短路径

1中南大学《数据结构》课程设计题目第9题Dijkstra算法求最短路径学生姓名XXXX指导教师XXXX学院信息科学与工程学院专业班级XXXXXXX完成时间XXXXXXX2目录第一章问题分析与任务定义---------------------------------------------------------------------31.1课程设计题目-----------------------------------------------------------------------------31.2原始数据的输入格式--------------------------------------------------------------------31.3实现功能-----------------------------------------------------------------------------------31.4测试用例-----------------------------------------------------------------------------------31.5问题分析-----------------------------------------------------------------------------------3第二章数据结构的选择和概要设计------------------------------------------------------------42.1数据结构的选择--------------------------------------------------------------------------42.2概要设计-----------------------------------------------------------------------------------4第三章详细设计与编码-----------------------------------------------------------------------------63.1框架的建立---------------------------------------------------------------------------------63.2点结构体的定义---------------------------------------------------------------------------73.3创立带权值有向图------------------------------------------------------------------------83.4邻接矩阵的显示---------------------------------------------------------------------------93.5递归函数的应用---------------------------------------------------------------------------103.6Dijkstra算法实现最短路径--------------------------------------------------------------10第四章上机调试------------------------------------------------------------------------------------114.1记录调试过程中错误和问题的处理---------------------------------------------------114.2算法的时间课空间性能分析------------------------------------------------------------114.3算法的设计、调试经验和体会---------------------------------------------------------11第五章测试结果-----------------------------------------------------------------------------------12第六章学习心得体会-----------------------------------------------------------------------------12第七章参考文献-----------------------------------------------------------------------------------12附录------------------------------------------------------------------------------------------------------123第一章问题分析与任务定义1、课程设计题目：1.1题目：采用适当的存储结构实现带权有向图的存储，建立，输入、显示，以及使用Dijkstra算法，寻找和输出带权有向图中某个源点到其余各点的最短路径1.2要求：采用适当的存储结构实现带权有向图的存储，建立，输入、显示，以及使用Dijkstra算法。1.3具体任务：建立图的存储模块，建立图的输出模块，在建图后从单源点开始求最短路径，并显示出来。2.原始数据的输入格式2.1建图：2.1.1数字2.2显示：2.2.1数字+逗号+数字+回车2.2.2字母+回车3.实现功能3.1建立有向图3.2显示存储的有向图3.3显示从顶点到其他各个顶点的最短路径和是否存在路径4.测试用例4.1正确数据：输入顶点；边值信息输出结果：最短路径是否存在，存在的情况最短路径是多少，其次是不存在。5.问题分析实现本程序要解决以下几个问题：5.1如何存储一个有向图。5.2如何在界面中输出该有向图。5.3如何定义起始源点。5.4如何选择出最短路径。5.5找到的最短路径如何输出。4第二章数据结构的选择和概要设计1.数据结构的选择：在图的结构中，任意两个顶点之间都可能存在关系，比线性表和树要复杂。由于不存在严格的前后顺序，因而不能采用简单的数组来存储图;另一方面，如果采用链表，由于图中各顶点的度数不尽相同，最小度数和最大度数可能相差很大，如果按最大度数的顶点来设计链表的指针域，则会浪费很多存储单元，反之，如果按照各个顶点设计不同的链表结点，则会给操作带来很大的困难。在此我选用邻接矩阵的存储结构。采用邻接矩阵存储，很容易判断图中两个顶点是否相连，也容易求出各个顶点的度。不过任何事情都不是完美的，采用邻接矩阵存储图时，测试其边的数目，必须检查边二维数组的所有元素，时间复杂度为O（n2）,这对于顶点很多而边较少的图（稀疏图）是非常不合算的。以邻接矩阵存储有向图。2.概要设计2.1对于最短路径问题：最短路径是在实际应用中非常有用的工具，我们常见的两种最短路径是：（1）从某源点到其余各顶点之间的最短路径。（2）每一段顶点之间的最短路径在这里我们解决第一类问题。2.2Dijkstra算法用于求最短路径：Dijkstra算法是按路径长度递增的次序逐步产生源点到其他顶点间的最短路径。算法建立一个顶点集合S，初始时该集合只有源点V0，然后逐步将已求得最短路径的顶点加入到集合中，直到全部顶点都在集合S中，算法结束。2..3Dijkstra算法思想设cost[i,j]=0，S为已经求得最短路径的顶点集合，distance[i]数组的每个元素表示当前状态下源点V0到Vi的最短路径。算法如下：1)初始化：S={V0},distance[i]=cost[0,i]。2)选择一个终点Vj，满足distance[j]=MIN{distance[i]|Vi∈V-S}。3）把Vj加入到S中。4）修改distance数组元素，修改逻辑为对于所有不在S中的顶点Vi.if(distance[j]+cost[i,j]distance[i]){distance[i]=5distance[j]]+cost[i,j]}5)重复操作2）、3）、4），直到全部顶点加入到S中。2.4实现流程在任意图中实现求最短路径问题，第一步是要能成功的在内存中输入图的信息，图的信息有两个，一是顶点个数，二是每两点之间的权值信息。当建立图之后，对图进行遍历才能使用Dijkstra算法求出最短路径；在完成了图的建立之后，用Dijkstra算法的思想，从单源点开始，求出到各个顶点的最短路径，并能够实现显示功能。程序流程图：输入顶点名称输入每条边的信息返回每个结点的位置创建图Dijkstra算法的实现D[w]n输出源点与其他点最短距离开始输入顶点边个数结束6(1)输入顶点个数n，边的条数，初始化邻接矩阵。(2)初始化所每条边的权值与D[h]中(3)①找出v0到图中其他各点的最小值②经过改最小值的点到除它外其他各点的最小值③直到s中的所有值全部被处理过，(4)输出各最短路径的长度D[w]算法的思想，从单源点开始，求出到各个顶点的最短路径，并能够实现显示功能。第三章详细设计和编码3.1框架的建立typedefcharVertexType;//定义图的顶点为字符型typedefintVRType;//顶点关系类型typedefintInfoType;//该弧相关信息typedefstructArcCell{VRTypeadj;//权值InfoType*info;//弧相关信息的指针}ArcCell;typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];//一维数组，存储顶点ArcCellarcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵：二维数组，存储边和弧intvexnum,arcnum;//图的当前顶点数和弧数}MGrph;//邻接矩阵表示的图3.1.1顶点的定义typedefcharVertexType;//定义图的顶点为字符型顶点的最大个数253.1.2ArcCellarcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];二维数组用于存放邻接矩阵，每个位置代表的值为图中的权值，其余用无穷大3000表示。3.2点结构体的定义/*确定位置函数*/intLocateVex(MGrph*G,VertexTypev){intj,b;7for(b=0;bG-vexnum;b++)//在所有顶点中寻找if(G-vexs[b]==v)//找到所找的顶点在b位置{j=b;break;}//ifreturn(j);}//LocateVex3.3创立带权值有向图首先输入该有向图的顶点数n,然后依次输入各个顶点及边长（输入的顶点的序号应该小于顶点的数目）。/*有向图的建立*/voidCreat_YG(MGrph*G){inti,k,j,n;VertexTypev1,v2;intw=1;printf(请输入顶点个数和弧数如括号里的方式（3,3）:);//读入顶点个数和弧的个数scanf(%d,%d,&G-vexnum,&G-arcnum);//读出边和弧的信息printf(\n);//换行输出for(i=0;iG-vexnum;i++){printf(请输入图的第%d个顶点:,w);//输入指定的顶点w++;fflush(stdin);scanf(%c,&G-vexs[i]);printf(\n);}for(i=0;iG-vexnum;i++)for(j=0;jG-vexnum;j++){G-arcs[i][j].adj=INFINITY;G-arcs[i][j].info=NULL;}for(k=0;kG-arcnum;k++){//输入各弧并