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

1、中南大学数据结构课程设计题目第9题Dijkstra算法求最短路径学生姓名XXXX指导教师XXXX学院信息科学与工程学院专业班级XXXXXXX完成时间XXXXXXX目录第一章问题分析与任务定义31.1 课程设计题目31.2 原始数据的输入格式31.3 实现功能31.4 测试用例31.5 问题分析3第二章数据结构的选择和概要设计41 数据结构的选择41 概要设计4第三章详细设计与编码63.4 框架的建立63.5 点结构体的定义73.6 创立带权值有向图83.7 邻接矩阵的显示93.8 递归函数的应用103.9 Dijkstra算法实现最短路径10第四章上机调试11记录调试过程中错误和问题的处理11

2、算法的时间课空间性能分析11算法的设计、调试经验和体会11第五章测试Z果12第六章学习心彳#体会12第七章参考文献12附录12第一章问题分析与任务定义1、课程设计题目：题目：采用适当的存储结构实现带权有向图的存储，建立，输入、显示，以及使用Dijkstra算法，寻找和输出带权有向图中某个源点到其余各点的最短路径要求：采用适当的存储结构实现带权有向图的存储，建立，输入、显示，以及使用Dijkstra算法。具体任务：建立图的存储模块，建立图的输出模块，在建图后从单源点开始求最短路径，并显示出来。.原始数据的输入格式建图：2.1.1数字显示：2.2.1数字+逗号+数字+回车2.2.2字母+回车.实现

3、功能建立有向图显示存储的有向图显示从顶点到其他各个顶点的最短路径和是否存在路径.测试用例正确数据：输入顶点；边值信息输出结果：最短路径是否存在，存在的情况最短路径是多少，其次是不存在。.问题分析实现本程序要解决以下几个问题：如何存储一个有向图。如何在界面中输出该有向图如何定义起始源点。如何选择出最短路径。找到的最短路径如何输出。第二章数据结构的选择和概要设计.数据结构的选择：在图的结构中，任意两个顶点之间都可能存在关系，比线性表和树要复杂。由于不存在严格的前后顺序，因而不能采用简单的数组来存储图；另一方面，如果采用链表，由于图中各顶点的度数不尽相同，最小度数和最大度数可能相差很大，如果按最大度

4、数的顶点来设计链表的指针域，则会浪费很多存储单元，反之，如果按照各个顶点设计不同的链表结点，则会给操作带来很大的困难。在此我选用邻接矩阵的存储结构。采用邻接矩阵存储，很容易判断图中两个顶点是否相连，也容易求出各个顶点的度。不过任何事情都不是完美的，采用邻接矩阵存储图时，测试其边的数目，必须检查边二维数组的所有元素，时间复杂度为O（n2）,这对于顶点很多而边较少的图（稀疏图）是非常不合算的。以邻接矩阵存储有向图。.概要设计对于最短路径问题：最短路径是在实际应用中非常有用的工具，我们常见的两种最短路径是：（1）从某源点到其余各顶点之间的最短路径。（2）每一段顶点之间的最短路径在这里我们解决第一类问

5、题。Dijkstra算法用于求最短路径：Dijkstra算法是按路径长度递增的次序逐步产生源点到其他顶点问的最短路径。算法建立一个顶点集合S,初始时该集合只有源点V0,然后逐步将已求得最短路径的顶点加入到集合中，直到全部顶点都在集合S中，算法结束。2.3Dijkstra算法思想设costi,j=0,S为已经求得最短路径的顶点集合，distancei数组的每个元素表示当前状态下源点V0到Vi的最短路径。算法如下：1）初始化：S=V0,distancei=cost0,i。2）选择一个终点Vj,满足distancej=MINdistancei|ViCV-S。3）把Vj加入到S中。4）修改distan

6、ce数组元素，修改逻辑为对于所有不在S中的顶点Vi.if(distancej+costi,j<distancej+costi,jdistancei)distancei=5）重复操作2）、3）、4）,直到全部顶点加入到S中2.4实现流程在任意图中实现求最短路径问题，第一步是要能成功的在内存中输入图的信息，图的信息有两个，一是顶点个数，二是每两点之间的权值信息。当建立图之后，对图进行遍历才能使用Dijkstra算法求出最短路径；在完成了图的建立之后，用Dijkstra算法的思想，从单源点开始，求出到各个顶点的最短路径，并能够实现显示功能。程序流程图：(1)输入顶点个数n,边的条数，初始化邻接

7、矩阵。(2)初始化所每条边的权值与Dh中(3)找出v0到图中其他各点的最小值经过改最小值的点到除它外其他各点的最小值直到s中的所有值全部被处理过，(4)输出各最短路径的长度Dw算法的思想，从单源点开始，求出到各个顶点的最短路径，并能够实现显示功能。第三章详细设计和编码框架的建立typedefcharVertexType;/定义图的顶点为字符型typedefintVRType;/顶点关系类型typedefintInfoType;/该弧相关信息typedefstructArcCellVRTypeadj;/权值InfoType*info;/弧相关信息的指针ArcCell;typedefstructV

8、ertexTypevexsMAX_VERTEX_NUM;/L维数组，存储顶点ArcCellarcsMAX_VERTEX_NUMMAX_VERTEX_NUMW矩阵：二维数组,存储边和弧intvexnum,arcnum;/图的当前顶点数和弧数MGrph;/邻接矩阵表示的图顶点的定义typedefcharVertexType;/定义图的顶点为字符型顶点的最大个数25ArcCellarcsMAX_VERTEX_NUMMAX_VERTEX_NUM轴数组用于存放令口接矩阵，每个位置代表而值为图中而权值，其余用无穷大3000表示。点结构体的定义/*确定位置函数*/intLocateVex(MGrph*G,V

9、ertexTypev)intj,b;for(b=0;b<G->vexnum;b+)/在所有顶点中寻找if(G->vexsb=v)找到所找的顶点在b位置j=b;break;/ifreturn(j);/LocateVex创立带权值有向图首先输入该有向图的顶点数n,然后依次输入各个顶点及边长(输入的顶点的序号应该小于顶点的数目)。/*有向图的建立*/voidCreat_YG(MGrph*G)(inti,k,j,n;VertexTypev1,v2;intw=1;printf("请输入顶点个数和弧数如括号里白方式(3,3):");/读入顶点个数和弧的个数scanf(

10、"%d,%d",&G->vexnum,&G->arcnum);/读出边和弧的信息printf("n");/换行输出for(i=0;i<G->vexnum;i+)(printf("请输入图的第%d个顶点：",w);/输入指定的顶点w+;fflush(stdin);scanf("%c",&G->vexsi);printf("n");for(i=0;i<G->vexnum;i+)for(j=0;j<G->vexnum;j+)

11、(G->arcsij.adj=INFINITY;G->=NULL;for(k=0;k<G->arcnum;k+)输入各弧并构造邻接矩阵printf("请输入边的起点和终点和权值如(v1,v2,n):");/起始点和终点和两点之间对应的权值fflush(stdin);scanf("%c,%c,%d”,&v1,&v2,&n);printf("n");i=LocateVex(G,v1);/确定v1的位置j=LocateVex(G,v2);/确定v2的位置G->arcs皿.ad

12、j=n;/边<v1,v2>的权值赋为1,如需要权值操作则相应修改一下即可G->=NULL;/如需要有相关信息则相对应输入，在这里我设置为空第二个forgetchar();/Creat_YGvoidjuzhen(MGrph*G)/用矩阵来存储并显示出结果inti,j,k;printf("邻接矩阵显示：n");printf("t");for(i=0;i<G->vexnum;i+)printf("t%5c”,G->vexsi);for(j=0;j<G->vexnum;j+)prin

13、tf("nn");printf("t%5c”,G->vexsj);for(k=0;k<G->vexnum;k+)if(G->arcsjk.adj<INFINITY)printf("t%5d”,G->arcs皿k.adj);elseprintf("t3000");/无权值的直接输出最大值邻接矩阵的显示在图的邻接矩阵显示中，分别利用for循环输出了矩阵的行列标，使矩阵很明了。voidjuzhen(MGrph*G)/用矩阵来存储并显示出结果inti,j,k;printf("邻接矩阵显示：n&qu

14、ot;);printf("t");for(i=0;i<G->vexnum;i+)printf("t%5c”,G->vexsi);for(j=0;j<G->vexnum;j+)printf("nn");printf("t%5c”,G->vexsj);for(k=0;k<G->vexnum;k+)if(G->arcsjk.adj<INFINITY)printf("t%5d",G->arcsjk.adj);elseprintf("t3000&qu

15、ot;);/无权值的直接输出最大值)递归函数应用思想是patn数组来表示前驱顶点的位置，然后递归输出每个顶点的前驱voidShort(MGrph*G,intpath,inti,intw)递归函数是用来输出从源点出发到终点之前的顶点思想是patn数组来表示前驱顶点的位置，然后递归输出每个顶点的前驱intk;k=pathi;if(k!=w)Short(G,path,k,w);printf("%c,",G->vexsk);/输出k位置的顶点值)Dijkstra算法实现最短路径设图以邻接矩阵cost存储，矩阵中各元素的值为各边的权值。顶点间无边时其对应权信用无穷大表示。从顶点

16、V0到其它各顶点间的最短路径的具体步骤如下：a)变量定义：定义整型数组S,这是一个顶点集合，初始时该集合只有源点v0,然后逐步将以求得最短路径的顶点加入到该集合中，直到全部顶点都在集合S中，算法结束。定义两个整型变量dis、mindis均用来标志图中最短的那一条路径。b)初始化：初始化dist数组的值即为cost数组中存放的权值。disti=costv0i初始化求到每个顶点的最短路径时都经过v0顶点。pathi.pnode0=v0初始化记录经过的顶点数都为0。pathi.num=0;初始化顶点集合s为空，即还未开始。si=0;c)源点的选择：将V0顶点加入到顶点集合s中。sv0=1d)利用fo

17、r循环选择一个终点Vj,使其满足V0到Vj距离最短，同时将Vj加入集合S中。e)根据j顶点调整当前的最短路径，若满足disti>distj+costji,则修改disti的值。同时V0到Vi的最短路径中经过的顶点数加1,即pathi.num+;并将经过的顶点存入数组pnode即pathi.pnodepathi.num=jf)此时一趟求最短路径完毕，将终点V1添加到路径中。g)循环执行d),e),f)操作，直到全部顶点加入到S中。第四章上机调试记录调试过程中错误和问题的处理1)当输入格式不符合程序要求时，会出现循环2)当两顶点间没有路径时，权值为无穷大，但在本程序中只能用一个具体的数字20

18、00代替抽象的无穷大。3)在程序的调试过程可暂时多加一些输出语句以便及时查看一下中间运行情况，并对程序规格说明作调整和改动。算法的时间和空间性能分析时间复杂度对于n个顶点的有向图，求一个顶点到其他顶点的最短路径的时间为O(n),调整最短路径的循环共执行n-1次，是二层循环，所以，时间复杂度是O(n2)。空间复杂度采用邻接矩阵存储有向图，应处理每两个顶点之间的关系，所以空间复杂度为O(n2)。算法设计、调试的经验和体会Dijkstra算法在上课的时候曾作为重点讲过，所以在做查找最短路径的算法时很流畅，但是在输出最短路径的时候遇到了很大的阻力。因为在定义结点时，使用的是结构体数组，所以当处理V0到

19、每个结点的最短路径时，导致无法具体记录经过的顶点数，只能记录源点、终点前一顶点以及终点。所以本程序在输出最短路径时有较大的瑕疵，还需进一步修改。第五章测试结果5.1测试结果:注意问题：1、输入顶点个数：最大不超过25,请输入罗马数字，若输入其他符号，无意义；2、以“字母字母数字”的格式输入图的信息，输入第一个字母为原点，第二个字母为终点，输入“数字”为权值，最后输入一个“字母”为顶点输入。输入完成；3、在输入完成后，屏幕显示邻接矩阵与最短路径。第六章学习心得体会通过对本次课程设计的学习与交流，使我学习到一部分很重要的关于编程方面思想，同时也获得了部分学习其他学科的方法。学习重在于体会，体会这种

20、学科给我带来的思考，给我带来由浅入深的演算心得。做一次课程设计，不仅仅是为了完成某项任务，而在于是否能从这次任务中总结出一些处理同类任务的方法和技巧。每次全力的付出，都会有或多或少的收获。通过对本次课程设计涉及的问题的分析和处理，了解到学习数据结构对编程的技巧和思想方法。以前也了解过数据结构相关的书籍，但没有深入的学习，本次上机课程设计从选题上也把学习的方法应用其中，在编程时算法的理解和分析十分重要，首先的弄懂它的基本框架，用什么来算法来实现，最后通过查找部分资料，修改调试，总结心得，就是一种进步。第七章参考文献:严蔚敏吴伟明编著的数据结构（C语言版）:杨晓波主编王弘王聪华胡永副主编的数据结构

21、实验指导（C语言版）附件：#include<stdio.h>#include<stdlib.h>#defineMAX_VERTEX_NUM25/最大顶点个数#defineINFINITY3000/最大值typedefcharVertexType;/定义图的顶点为字符型typedefintVRType;/顶点关系类型typedefintInfoType;/该弧相关信息typedefstructArcCellVRTypeadj;/权值InfoType*info;弧相关信息的指针ArcCell;typedefstructVertexTypevexsMAX_VERTEX_NUM

22、;/一维数组，存储顶点ArcCellarcsMAX_VERTEX_NUMMAX_VERTEX_NUM;邻接矩阵：二维数组，存储边和弧intvexnum,arcnum;/图的当前顶点数和弧数MGrph;邻接矩阵表示的图/*确定位置函数*/intLocateVex(MGrph*G,VertexTypev)intj,b;for(b=0;b<G->vexnum;b+)/在所有顶点中寻找if(G->vexsb=v)找到所找的顶点在b位置j=b;break;/ifreturn(j);/LocateVex/*有向图的建立*/voidCreat_YG(MGrph*G)inti,k,j,n;V

23、ertexTypev1,v2;intw=1;printf("请输入顶点个数和弧数如括号里白方式(3,3):");/读入顶点个数和弧的个数scanf("%d,%d",&G->vexnum,&G->arcnum);/读出边和弧的信息printf("n");/换行输出for(i=0;i<G->vexnum;i+)printf("请输入图的第%d个顶点：",w);/输入指定的顶点w+;fflush(stdin);scanf("%c",&G->vexs

24、i);printf("n");for(i=0;i<G->vexnum;i+)for(j=0;j<G->vexnum;j+)G->arcsij.adj=INFINITY;G->=NULL;for(k=0;k<G->arcnum;k+)输入各弧并构造邻接矩阵printf("请输入边的起点和终点和权值如(v1,v2,n):");起始点和终点和两点之间对应的权值fflush(stdin);scanf("%c,%c,%d",&v1,&v2,&n);pr

25、intf("n");i=LocateVex(G,v1);确定v1的位置j=LocateVex(G,v2);确定v2的位置G->arcsij.adj=n;/边71,丫2>的权值赋为1,如需要权值操作则相应修改一下即可G->=NULL;/如需要有相关信息则相对应输入，在这里我设置为空第二个forgetchar();/Creat_YGvoidjuzhen(MGrph*G)/用矩阵来存储并显示出结果inti,j,k;printf("邻接矩阵显示：n");printf("t");for(i=0;i<

26、G->vexnum;i+)printf("t%5c",G->vexsi);for(j=0;j<G->vexnum;j+)printf("nn");printf("t%5c",G->vexsj);for(k=0;k<G->vexnum;k+)if(G->arcsjk.adj<INFINITY)printf("t%5d",G->arcsjk.adj);elseprintf("t3000");/无权值的直接输出最大值voidShort(MGr

27、ph*G,intpath口,inti,intw)递归函数是用来输出从源点出发到终点之前的顶点思想是patn数组来表示前驱顶点的位置，然后递归输出每个顶点的前驱intk;k=pathi;if(k!=w)Short(G,path,k,w);printf("%c,",G->vexsk);输出k位置的顶点值)voidShortestPath(MGrph*G,intw)/Dijkstrs算法应用inti,k,m,n,min;intfinal30,path30,D30;定义三个数组，final标记该顶点是否在最短路径上/path口用来记录顶点的前驱顶点的位置，D口是用来记录从源点到该点的最短路径长度for(i=0;i<G->vexnum;i+)pathi=w;/首先把所有顶点的前驱顶点的位置赋值为w位置，也就