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

中南大学数据结构课程设计 题 目 第9题 Dijkstra算法求最短路径 学生姓名 XXXX 指导教师 XXXX 学 院 信息科学与工程学院 专业班级 XXXXXXX 完成时间 XXXXXXX 目录第1章 问题分析与任务定义-3 1.1 课程设计题目-3 1.2 原始数据的输入格式-3 1.3 实现功能-3 1.4 测试用例-3 1.5 问题分析-3第2章 数据结构的选择和概要设计-4 2.1 数据结构的选择-4 2.2 概要设计-4第3章 详细设计与编码-6 3.1 框架的建立-6 3.2 点结构体的定义-7 3.3 创立带权值有向图-8 3.4 邻接矩阵的显示-9 3.5 递归函数的应用-10 3.6 Dijkstra算法实现最短路径-10第4章 上机调试-11 4.1 记录调试过程中错误和问题的处理-11 4.2 算法的时间课空间性能分析-11 4.3 算法的设计、调试经验和体会-11第5章 测试结果-12第6章 学习心得体会-12第7章 参考文献-12附录-12第1章 问题分析与任务定义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找到的最短路径如何输出。第2章 数据结构的选择和概要设计1.数据结构的选择： 在图的结构中，任意两个顶点之间都可能存在关系，比线性表和树要复杂。由于不存在严格的前后顺序，因而不能采用简单的数组来存储图;另一方面，如果采用链表，由于图中各顶点的度数不尽相同，最小度数和最大度数可能相差很大，如果按最大度数的顶点来设计链表的指针域，则会浪费很多存储单元，反之，如果按照各个顶点设计不同的链表结点，则会给操作带来很大的困难。 在此我选用邻接矩阵的存储结构。采用邻接矩阵存储，很容易判断图中两个顶点是否相连，也容易求出各个顶点的度。不过任何事情都不是完美的，采用邻接矩阵存储图时，测试其边的数目，必须检查边二维数组的所有元素，时间复杂度为O（n2）,这对于顶点很多而边较少的图（稀疏图）是非常不合算的。以邻接矩阵存储有向图。2.概要设计2.1对于最短路径问题：最短路径是在实际应用中非常有用的工具，我们常见的两种最短路径是：（1）从某源点到其余各顶点之间的最短路径。（2）每一段顶点之间的最短路径在这里我们解决第一类问题。2.2 Dijkstra算法用于求最短路径：Dijkstra算法是按路径长度递增的次序逐步产生源点到其他顶点间的最短路径。算法建立一个顶点集合S，初始时该集合只有源点V0，然后逐步将已求得最短路径的顶点加入到集合中，直到全部顶点都在集合S中，算法结束。 2.3 Dijkstra算法思想设costi,j=0，S为已经求得最短路径的顶点集合，distancei数组的每个元素表示当前状态下源点V0到Vi的最短路径。算法如下：1) 初始化：S=V0, distancei=cost0,i。2) 选择一个终点Vj，满足distancej=MIN distancei|ViV-S。3）把Vj加入到S中。4）修改distance数组元素，修改逻辑为对于所有不在S中的顶点Vi.if(distancej+costi,j distancei) distancei= distancej +costi,j 5) 重复操作2）、3）、4），直到全部顶点加入到S中。输入顶点名称输入每条边的信息返回每个结点 的位置创建图Dijkstra算法的实现Dwn输出源点与其他点最短距离开始输入顶点边个数结束2.4 实现流程在任意图中实现求最短路径问题，第一步是要能成功的在内存中输入图的信息，图的信息有两个，一是顶点个数，二是每两点之间的权值信息。当建立图之后，对图进行遍历才能使用Dijkstra算法求出最短路径；在完成了图的建立之后，用Dijkstra算法的思想，从单源点开始，求出到各个顶点的最短路径，并能够实现显示功能。 程序流程图：(1) 输入顶点个数n，边的条数，初始化邻接矩阵。(2)初始化所每条边的权值与Dh中(3) 找出v0到图中其他各点的最小值 经过改最小值的点到除它外其他各点的最小值 直到s中的所有值全部被处理过， (4) 输出各最短路径的长度Dw算法的思想，从单源点开始，求出到各个顶点的最短路径，并能够实现显示功能。第3章 详细设计和编码3.1框架的建立typedef char VertexType;/定义图的顶点为字符型 typedef int VRType; /顶点关系类型typedef int InfoType;/该弧相关信息 typedef struct ArcCellVRType adj;/权值 InfoType *info;/弧相关信息的指针ArcCell;typedef structVertexType vexsMAX_VERTEX_NUM;/一维数组，存储顶点ArcCell arcsMAX_VERTEX_NUMMAX_VERTEX_NUM;/邻接矩阵 ：二维数组，存储边和弧int vexnum,arcnum;/图的当前顶点数和弧数 MGrph;/邻接矩阵表示的图3.1.1顶点的定义typedef char VertexType;/定义图的顶点为字符型 顶点的最大个数253.1.2ArcCell arcsMAX_VERTEX_NUMMAX_VERTEX_NUM;二维数组用于存放邻接矩阵，每个位置代表的值为图中的权值，其余用无穷大3000表示。3.2点结构体的定义/* 确定位置函数 */int LocateVex(MGrph *G,VertexType v) int j,b; for(b=0;bvexnum;b+)/在所有顶点中寻找 if(G-vexsb=v)/找到所找的顶点在b位置 j=b; break; /ifreturn(j); /LocateVex3.3创立带权值有向图首先输入该有向图的顶点数n,然后依次输入各个顶点及边长（输入的顶点的序号应该小于顶点的数目）。/* 有向图的建立 */void Creat_YG(MGrph *G)int i,k,j,n; VertexType v1,v2; int w=1;printf(请输入顶点个数和弧数 如括号里的方式（3,3）:);/读入顶点个数和弧的个数scanf(%d,%d,&G-vexnum,&G-arcnum);/读出边和弧的信息 printf(n); /换行输出 for(i=0;ivexnum;i+) printf(请输入图的第%d个顶点:,w);/输入指定的顶点 w+; fflush(stdin); scanf(%c,&G-vexsi); printf(n); for(i=0;ivexnum;i+) for(j=0;jvexnum;j+) G-arcsij.adj=INFINITY; G-arcsij.info=NULL; for(k=0;karcnum;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-arcsij.adj=n;/边的权值赋为1，如需要权值操作则相应修改一下即可 G-arcsij.info=NULL;/如需要有相关信息则相对应输入，在这里我设置为空 /第二个forgetchar(); /Creat_YGvoid juzhen(MGrph *G)/用矩阵来存储并显示出结果 int i,j,k; printf(邻接矩阵显示：n); printf(t); for(i=0;ivexnum;i+) printf(t%5c,G-vexsi); for(j=0;jvexnum;j+) printf(nn); printf(t%5c,G-vexsj); for(k=0;kvexnum;k+) if(G-arcsjk.adjarcsjk.adj); else printf(t 3000); /无权值的直接输出最大值 3.4邻接矩阵的显示在图的邻接矩阵显示中，分别利用for循环输出了矩阵的行列标，使矩阵很明了。void juzhen(MGrph *G)/用矩阵来存储并显示出结果 int i,j,k; printf(邻接矩阵显示：n); printf(t); for(i=0;ivexnum;i+) printf(t%5c,G-vexsi); for(j=0;jvexnum;j+) printf(nn); printf(t%5c,G-vexsj); for(k=0;kvexnum;k+) if(G-arcsjk.adjarcsjk.adj); else printf(t 3000); /无权值的直接输出最大值 3.5递归函数应用3.5.1思想是patn数组来表示前驱顶点的位置，然后递归输出每个顶点的前驱void Short(MGrph *G,int path,int i,int w) /递归函数是用来输出从源点出发到终点之前的顶点 /思想是patn数组来表示前驱顶点的位置，然后递归输出每个顶点的前驱 int k; k=pathi; if(k!=w) Short(G,path,k,w ); printf(%c,G-vexsk);/输出k位置的顶点值 3.6 Dijkstra 算法实现最短路径设图以邻接矩阵cost存储，矩阵中各元素的值为各边的权值。顶点间无边时其对应权值用无穷大表示。从顶点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) 利用for循环选择一个终点Vj,使其满足V0到Vj距离最短，同时将Vj加入集合S中。e) 根据j顶点调整当前的最短路径，若满足disti distj+costji,则修改disti的值。同时V0到Vi的最短路径中经过的顶点数加1，即pathi.num+; 并将经过的顶点存入数组pnode即pathi.pnodepathi.num=j f) 此时一趟求最短路径完毕，将终点V1添加到路径中。g) 循环执行d),e),f)操作，直到全部顶点加入到S中。第4章 上机调试4.1记录调试过程中错误和问题的处理 1) 当输入格式不符合程序要求时，会出现循环2) 当两顶点间没有路径时，权值为无穷大，但在本程序中只能用一个具体的数字2000代替抽象的无穷大。3) 在程序的调试过程可暂时多加一些输出语句以便及时查看一下中间运行情况，并对程序规格说明作调整和改动。4.2算法的时间和空间性能分析4.2.1时间复杂度对于n个顶点的有向图，求一个顶点到其他顶点的最短路径的时间为O(n)，调整最短路径的循环共执行n-1次，是二层循环，所以，时间复杂度是O（n2）。4.2.2空间复杂度 采用邻接矩阵存储有向图，应处理每两个顶点之间的关系，所以空间复杂度为O（n2）。4.3算法设计、调试的经验和体会 Dijkstra算法在上课的时候曾作为重点讲过，所以在做查找最短路径的算法时很流畅，但是在输出最短路径的时候遇到了很大的阻力。因为在定义结点时，使用的是结构体数组，所以当处理V0到每个结点的最短路径时，导致无法具体记录经过的顶点数，只能记录源点、终点前一顶点以及终点。所以本程序在输出最短路径时有较大的瑕疵，还需进一步修改。第5章 测试结果5.1测试结果：注意问题：1、输入顶点个数：最大不超过25，请输入罗马数字，若输入其他符号，无意义；2、以“字母 字母 数字”的格式输入图的信息，输入第一个字母为原点，第二个字母为终点，输入“数字”为权值，最后输入一个“字母”为顶点输入。输入完成； 3、在输入完成后，屏幕显示邻接矩阵与最短路径。第6章 学习心得体会 通过对本次课程设计的学习与交流，使我学习到一部分很重要的关于编程方面思想，同时也获得了部分学习其他学科的方法。学习重在于体会，体会这种学科给我带来的思考，给我带来由浅入深的演算心得。做一次课程设计，不仅仅是为了完成某项任务，而在于是否能从这次任务中总结出一些处理同类任务的方法和技巧。每次全力的付出，都会有或多或少的收获。通过对本次课程设计涉及的问题的分析和处理，了解到学习数据结构对编程的技巧和思想方法。以前也了解过数据结构相关的书籍，但没有深入的学习，本次上机课程设计从选题上也把学习的方法应用其中，在编程时算法的理解和分析十分重要，首先的弄懂它的基本框架，用什么来算法来实现，最后通过查找部分资料，修改调试，总结心得，就是一种进步。第7章 参考文献6.1：严蔚敏 吴伟明 编著的数据结构（C语言版）6.2：杨晓波 主编 王 弘 王聪华 胡 永 副主编的数据结构实验指导（C语言版）附件：#include#include#define MAX_VERTEX_NUM 25 /最大顶点个数#define INFINITY 3000/最大值typedef char VertexType;/定义图的顶点为字符型 typedef int VRType; /顶点关系类型typedef int InfoType;/该弧相关信息 typedef struct ArcCellVRType adj;/权值 InfoType *info;/弧相关信息的指针ArcCell;typedef structVertexType vexsMAX_VERTEX_NUM;/一维数组，存储顶点ArcCell arcsMAX_VERTEX_NUMMAX_VERTEX_NUM;/邻接矩阵 ：二维数组，存储边和弧int vexnum,arcnum;/图的当前顶点数和弧数 MGrph;/邻接矩阵表示的图/* 确定位置函数 */int LocateVex(MGrph *G,VertexType v) int j,b; for(b=0;bvexnum;b+)/在所有顶点中寻找 if(G-vexsb=v)/找到所找的顶点在b位置 j=b; break; /ifreturn(j); /LocateVex/* 有向图的建立 */void Creat_YG(MGrph *G)int i,k,j,n; VertexType v1,v2; int w=1;printf(请输入顶点个数和弧数 如括号里的方式（3,3）:);/读入顶点个数和弧的个数scanf(%d,%d,&G-vexnum,&G-arcnum);/读出边和弧的信息 printf(n); /换行输出 for(i=0;ivexnum;i+) printf(请输入图的第%d个顶点:,w);/输入指定的顶点 w+; fflush(stdin); scanf(%c,&G-vexsi); printf(n); for(i=0;ivexnum;i+) for(j=0;jvexnum;j+) G-arcsij.adj=INFINITY; G-arcsij.info=NULL; for(k=0;karcnum;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-arcsij.adj=n;/边的权值赋为1，如需要权值操作则相应修改一下即可 G-arcsij.info=NULL;/如需要有相关信息则相对应输入，在这里我设置为空 /第二个forgetchar(); /Creat_YGvoid juzhen(MGrph *G)/用矩阵来存储并显示出结果 int i,j,k; printf(邻接矩阵显示：n); printf(t); for(i=0;ivexnum;i+) printf(t%5c,G-vexsi); for(j=0;jvexnum;j+) printf(nn); printf(t%5c,G-vexsj); for(k=0;kvexnum;k+) if(G-arcsjk.adjarcsjk.adj); else printf(t 3000); /无权值的直接输出最大值 void Short(MGrph *G,int path,int i,int w) /递归函数是用来输出从源点出发到终点之前的顶点 /思想是patn数组来表示前驱顶点的位置，然后递归输出每个顶点的前驱 int k; k=pathi; if(k!=w) Short(G,path,k,w ); printf(%c,G-vexsk);/输出k位置的顶点值 void ShortestPath(MGrph *G,int w) /Dijkstrs算法应用int i,k,m,n,min; int final30,path30,D30;/定义三个数组，final标记该顶点是否在最短路径上 /path用来记录顶点的前驱顶点的位置，D是用来记录从源点到该点的最短路径长度 for(i=0;ivexnum;i+) pathi=w;/首先把所有顶点的前驱顶点的位置赋值为w位置，也就是源点的位置 finali=0;/这是一个标记数组，一开始所有顶点位置对应的数组值全部标记为0 Di=G-arcswi.adj;/D是用来记录最短路径的长度，一开始把所有顶点到源点的的距离赋值给它 Dw=0;finalw=1;pathw=-100;/源点位置的Dw为0，finalw=1标记已经入集合，pathw=-100，表示该前驱为-100 for(m=1;mvexnum;m+) min=INFINITY;/首先赋值为机内最大值 for(k=0;kvexnum;k+) if(!finalk) if(Dkmin)i=k;min=Dk;/最短路径长度 finali=1;for(n=0;nvexnum;n+)if(!finaln&(min+G-arcsin.adj)arcsin.adj; pathn=i; /if /for for(m=0;mvexnum;m+) if(finalm=1&m!=w) printf(t从%c到%c的最短路径长度为：%dt路径是：,G-vexsw,G-vexsm,Dm);/输出最大值时则表示两点之间没有最短路径 Short(G,path,m,w); printf(%c,G-vexsm); printf(n); else printf(t从%c到%c没有不存在路径！n,G-vexsw,G-vexsm);/判断是否存在最短路径 main() MGrph m; VertexType ch; int j; Creat_YG(&m); juzhen(&m); printf(n请输入要开始的顶点:); scanf(%c,&ch); j=LocateVex(&m,ch); getchar(); ShortestPath(&m,j); getchar();