Dijkstra算法的实现-数据结构与算法课程设计报告.doc

合肥学院计算机科学与技术系课程设计报告2009 2010 学年第 2 学期课程 数据结构与算法课程设计名称Dijkstra算法的实现学生姓名张睿辰学号0804012044专业班级08计科(2)班指导教师王昆仑 张贯虹2010 年 6月Dijkstra算法的实现一、 问题分析与任务定义1、课程设计题目：1.1题 目：对任意图，选择合适的数据结构表示图，在此基础上实现求解最短路径的Dijkstra算法1.2 要 求：设计合理的数据结构存储图，简单有效的实现Dijkstra算法。1.3具体任务：建立图的存储模块，建立图的输出模块，在建图后从单源点开始求最短路径，并显示出来！2、原始数据的输入格式：2.1建图模块： 2.1.1 数字2.2.2 数字+空格+数字+空格+数字+回车2.3显示模块：回车3、实现功能： 3.1 建立有向图3.2 显示存储的有向图 3.3 显示从顶点到其他各顶点的最短路径4、测试用例： 4.1正确数据：a）顶点：3；边值信息：0 1 6；0 2 4；1 2 5；2 0 6；0 0 0； b）顶点：0；边值信息：0 0 0； 输出结果：a) v0到v1的最短路径是6，v0到v2的最短路径是4 b) 没有最短路径 4.2错误数据：a) 顶点：ab）顶点：2；边值信息：0 3 6；0 4 4；13 5； 0 0 0； c）顶点：3；边值信息：0 1 a； 输出结果：边值错误，请从新输入5、问题分析： 实现本程序要解决以下几个问题：5.1如何存储一个有向图。5.2如何在界面中输出该有向图。5.3如何定义起始源点。5.4如何选择出最短路径。5.5找到的最短路径如何输出。二、 数据结构的选择和概要设计1、 数据结构的选择： 在图的结构中，任意两个顶点之间都可能存在关系，比线性表和树要复杂。由于不存在严格的前后顺序，因而不能采用简单的数组来存储图;另一方面，如果采用链表，由于图中各顶点的度数不尽相同，最小度数和最大度数可能相差很大，如果按最大度数的顶点来设计链表的指针域，则会浪费很多存储单元，反之，如果按照各个顶点设计不同的链表结点，则会给操作带来很大的困难。 在此我选用邻接矩阵的存储结构。采用邻接矩阵存储，很容易判断图中两个顶点是否相连，也容易求出各个顶点的度。不过任何事情都不是完美的，采用邻接矩阵存储图时，测试其边的数目，必须检查边二维数组的所有元素，时间复杂度为O（n2）,这对于顶点很多而边较少的图（稀疏图）是非常不合算的。以邻接矩阵存储有向图，如图1中有向图G所示，其邻接矩阵为图 2 cost。 15364245105020153031510200501045015501020015200353000335图2. 有向图 图2.矩阵cost有向图的邻接矩阵costij定义为 int cost nn; 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中。2.4 实现流程在任意图中实现求最短路径问题，第一步是要能成功的在内存中输入图的信息，图的信息有两个，一是顶点个数，二是每两点之间的权值信息。当建立图之后，对图进行遍历才能使用Dijkstra算法求出最短路径；在完成了图的建立之后，用Dijkstra算法的思想，从单源点开始，求出到各个顶点的最短路径，并能够实现显示功能。 程序流程图：建 图输入顶点与边值信息定义顶点个数开始Dijkstra算法求最短路径显示最短路径结束Dijkstra算法流程图：N设定变量，初始化dist数组，使其与costV0i相对应定义顶点V0与自身的距离为0;定义经过的顶点个数为0；定义顶点集合SMAX初始化数组Si，并规定i为顶点序号将起点V0加入数组首先初始最短路径mindis为无穷大；查找离顶点V0最近的顶点，并赋值距离给mindis=distj;根据找到的顶点寻找下一个路径最短的顶点Su，并记录最短路径dis=distu+costj；dis是否大于V0直接到Su的距离； 最短路径为dist记录经过的顶点;j为寻找下一个顶点的变量添加顶点到最短路径当中；输出顶点V0到各个顶点的最短路径结束三、 详细设计和编码3.1邻接矩阵的定义：我们定义全局变量cost,dist数组，方便在各子程序中的调用，加快了程序的运行速度。int costMAXMAX; int distMAX; int n; cost二维数组用于存放邻接矩阵，每个位置代表的值为图中的权值，其余用无穷大999表示。dist为辅助数组，图中每个顶点对应该数组中的一个元素，这个元素存放当前源点到该顶点的最短路径。 此时的路径指示当前结果，并不一定是最终的最短路径。随着集合S的变化，其他顶点不断地加入到集合中，可能以这些新加入的顶点为“桥梁”产生比以前路径更短的路径，dist数组元素的值是动态变化的。n是指图中的顶点数目。3.2结点结构体的定义：struct int num; int pnodeMAX; pathMAX; 整型变量num是用来记录求V0到每个顶点的最短路径时所经过的顶点的数目。数组pnode用来存放求V0到每个顶点的最短路径时所经过的顶点，初始为V0。结构体数组path为从V0到各顶点的最短路径。3.3创建带权有向图初始化邻接矩阵cost中的值为无穷大，即任意两个顶点之间不存在路径。首先输入该有向图的顶点数n,然后依次输入各个顶点及边长（输入的顶点的序号应该小于顶点的数目）。输入0 0 0结束。定义变量contin，标志输入是否结束。若contin=1，输入继续，若contin=0，输入完成。代码：void creatgraph() /创建带权有向图int i,j,s,e,len,contin=1; printf("n请输入顶点个数:");scanf("%d",&n);for(i=0;i<n;i+)for(j=0;j<n;j+)costij=up;costji=up; /初始化所有顶点间的边值均为无穷大 costii=0; /每个顶点到自己的边值为0printf("输入各边，以0，0，0表示结束:n");i=1; /标志边的数目while(contin=1)printf("t第%d条边->顶点，顶点，边长:",i);scanf("%d%d%d",&s,&e,&len);if(s=0 && e=0 && len=0)contin=0;else if(s>=0 && s<n && e>=0 && e<n && len>0) /输入的顶点的序号应该小于顶点的数目costse=len;i+;elseprintf("tt边值错误，重复输入!n");display(n);/输出所建数组getchar();3.4邻接矩阵的显示在图的邻接矩阵显示中，分别利用for循环输出了矩阵的行列标，使矩阵很明了。代码：void display(int n1)int i,j;printf("n*所建图的邻接矩阵*n");for(i=0;i<n1;i+) printf("_%d_",i); /利用for循环输出邻接矩阵的行标printf("n"); for(i=0;i<n1;i+) printf("%d",i); /利用for循环输出邻接矩阵的列标 for(j=0;j<n1;j+) printf("t%3d<%d,%d>",costij,i,j); printf("n"); 3.5 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中。代码：void shortdjs() /求最短路径int sMAX; int mindis,dis,i,j,v0=0,u=0; /mindis标志图中最短的那一条路径for(i=0;i<n;i+)/初始化disti=costv0i; pathi.pnode0=v0;pathi.num=0; si=0; sv0=1; for(i=1;i<n;i+)/将最短路径定点加入到s中mindis=up; for(j=1;j<n;j+) /查找当前的最短路径if(sj=0 && distj<mindis)u=j; mindis=distj;su=1; for(j=1;j<n;j+)/根据j定点调整当前的最短路径if(sj=0)dis=distu+costuj; if(distj>dis) distj=dis; pathj.num+; pathj.pnodepathj.num=u;pathi.num+; pathi.pnodepathi.num=i;3.6最短路径的输出这段函数主要运用for循环，依次输出V 0到Vi的最短长度与最短路径。void dispath() /输出最短路径int i,j;printf("n从V0到各顶点的最短路径长度如下：n");printf("(起点->终点) 最短长度 最短路径n");printf("- - -n");for(i=1;i<n;i+)printf("(V0->V%d): ",i);if(disti<up)printf("t %d t<",disti);elseprintf("t t<"); /显示无穷大for(j=0;j<pathi.num;j+)printf("V%d->",pathi.pnodej);printf("V%d>n",pathi.pnodepathi.num);四、 上机调试41记录调试过程中遇到的错误和问题 a) 当输入格式不符合程序要求时，会提示错误输入，但会出现死循环，可以定义一个标志量contin，当要停止的时候，命令contin=0，循环结束；b) 当两顶点间没有路径时，权值为无穷大，但在本程序中只能用一个具体的数字999代替抽象的无穷大。c) 在程序的调试过程可暂时多加一些输出语句以便及时查看一下中间运行情况，并对程序规格说明作调整和改动。4.2算法的时间和空间性能分析4.2.1时间复杂度对于n个顶点的有向图，求一个顶点到其他顶点的最短路径的时间为O(n)，调整最短路径的循环共执行n-1次，是二层循环，所以，时间复杂度是O（n2）。4.2.2空间复杂度 采用邻接矩阵存储有向图，应处理每两个顶点之间的关系，所以空间复杂度为O（n2）。4.3算法设计、调试的经验和体会 Dijkstra算法在上课的时候曾作为重点讲过，所以在做查找最短路径的算法时很流畅，但是在输出最短路径的时候遇到了很大的阻力。因为在定义结点时，使用的是结构体数组，所以当处理V0到每个结点的最短路径时，导致无法具体记录经过的顶点数，只能记录源点、终点前一顶点以及终点。所以本程序在输出最短路径时有较大的瑕疵，还需进一步修改。五、 测试结果测试1：验证当两点间不存在路径时，程序是否正确。当顶点间无路径时，最短路径为无穷大。程序正确。测试2：输入一组正确的数据，测试程序的正确性。通过测试，验证了程序是正确的。测试3：测试当输入错误的时，程序是否正确。当输入错误时，提示重新输入，程序正确。六、 用户使用说明该程序可应用在出行指南中，用020表示出行地点，输入路径，得出最优出行路线。用户操作方法如下：1、输入顶点个数：最大不超过20，请输入罗马数字，若输入其他符号，会显示警告；2、以“数字 数字 数字”的格式输入图的信息，输入的数字0即表示源点，前两个数字应小于顶点个数，最后一个数字应小于999。当输入“0 0 0”时，输入完成；3、在输入完成后，屏幕显示邻接矩阵与最短路径。七、 参考文献1、王昆仑,李红编著. 数据结构与算法. 北京:中国铁道出版社,2007.2、严蔚敏,陈文博编著. 数据结构及算法教程. 北京: 清华大学出版社,2001八、 附录#include<iostream.h>#include<stdio.h>#include<string> #define MAX 20 /最多顶点个数#define up 999 /定义一个无穷大的值int costMAXMAX; /cost为带权邻接矩阵int distMAX,n; /dist为辅助数组，每个顶点对应该数组中的一个元素，这个元素存放当前源点到该顶点的最短路径。 struct int num; /记录求v0到每个顶点的最短路径时所经过的顶点的数目int pnodeMAX; /用来存放求v0到每个顶点的最短路径时所经过的顶点，初始为v0pathMAX; /path为从V0到各顶点的最短路径void display(int n1)int i,j;printf("n*所建图的邻接矩阵*n");for(i=0;i<n1;i+) printf("_%d_",i); /利用for循环输出邻接矩阵的行标printf("n"); for(i=0;i<n1;i+) printf("%d",i); /利用for循环输出邻接矩阵的列标 for(j=0;j<n1;j+) printf("t%3d<%d,%d>",costij,i,j); printf("n"); /输出所建图的邻接矩阵void creatgraph() /创建带权有向图int i,j,s,e,len,contin=1; /contin为标志变量，当contin=1时表示输入正确，当contin=0时，表示输入结束 printf("n请输入顶点个数:");scanf("%d",&n);for(i=0;i<n;i+)for(j=0;j<n;j+)costij=up; costji=up; /初始化所有顶点间的边值均为无穷大 costii=0; /每个顶点到自己的边值为0printf("输入各边，以0，0，0表示结束:n");i=1; /标志边的数目while(contin=1)printf("t第%d条边->顶点，顶点，边长:",i);scanf("%d%d%d",&s,&e,&len);if(s=0 && e=0 && len=0) contin=0;else if(s>=0 && s<n && e>=0 && e<n && len>0) /输入的顶点的序号应该小于顶点的数目costse=len;i+;else printf("tt边值错误，重复输入!n");display(n);/输出所建数组getchar();void shortdjs() /求最短路径int sMAX; /顶点集合，初始时该集合只有源点v0，然后逐步将以求得最短路径的顶点加入到该集合中，直到全部顶点都在集合S中，算法结束int mindis,dis,i,j,v0=0,u=0; /mindis标志图中最短的那一条路径for(i=0;i<n;i+)/初始化disti=costv0i; /初始化dist数组，顶点v0 v1 v2是与0 1 2 一一对应的pathi.pnode0=v0; /初始化求到每个顶点的最短路径时都经过v0顶点pathi.num=0; /初始化记录经过的顶点数都为0si=0; /顶点集合s为空，即还未开始sv0=1; /vo定点加入到s中，等于1表示已进入该集合for(i=1;i<n;i+)/将最短路径定点加入到s中mindis=up; /记录最短路径for(j=1;j<n;j+) /查找当前的最短路径if(sj=0 && distj<mindis)u=j; /找到离上一个顶点距离最短的结点mindis=distj;/将v0到此结点的距离赋值给mindissu=1; /u定点加入到s中，u记录的是距v0最短的顶点for(j=1;j<n;j+)/根据j定点调整当前的最短路径if(sj=0)dis=distu+costuj; /计算经过u结点 ，v0到j这个结点的距离if(distj>dis) /如果v0直接到j的距离，大于经过u结点， v0到j结点的距离distj=dis; /最短距离记录为distpathj.num+; /记录经过的顶点数 pathj.pnodepathj.num=u; /记录经过的结点pathi.num+; /将终点i添加到路径中pathi.pnodepathi.num=i;void dispath() /输出最短路径/system("cls");int i,j;printf("n从V0到各顶点的最短路径长度如下：n");printf("(起点->终点) 最短长度 最短路径n");printf("- - -n");for(i=1;i<n;i+)printf("(V0->V%d): ",i);if(disti<up)printf("t %d t<",disti);elseprintf("t t<"); /显示无穷大for(j=0;j<pathi.num;j+)printf("V%d->",pathi.pnodej);printf("V%d>n",pathi.pnodepathi.num); /只输出源点、终点、终点的前一顶点。void main()int i,p=3;for(i=0;i<p;i+) printf("*n",i);printf("*n",i); printf("* 欢迎使用迪杰斯特拉算法实现在任意图中求最短路径! *n");printf("*n",i); int j,q=3; for(j=0;j<q;j+) printf("* *n",j);creatgraph(); shortdjs();dispath(); getchar();getchar();