求解最短路径的Dijkstra算法

1、一、问题分析与任务定义本题主要是利用Dijkstra算法来求解顶点之间最短路径，其中包括如下几个待解决的问题：1问题分析选择合适的结构表示图主要包括：用Dijkstra算法实现起来更要容易；时间复杂度小；自己可以熟练应用。Dijstra算法的实现所应涉及到的各参数及变量：顶点的编号；各边权的初使化；如何求出从顶点到其他各点的最短距离；最短距离长度的求取等问题。2任务定义对任意图，选择合适的数据结构表示图，在此基础上实现求解最短路径的算法。要求：对所设计的图的数据结构，提供必要的基本功能。在带权的有向图中源点到终点的多条路径中寻找出一条各边权植之和最小的路径，即最短路径。对任务的理解考虑设计的图

2、结构是否具备必要的基本功能，具有实际的应用；图的邻接矩阵如何实现交互式；如何将输入的邻接矩阵溶入到dijstra算法中去。需要解决什么样的实际问题。并且能够将程序与实际问题相结合，能够处理一般的最短路径问题。二、概要设计和数据结构的选择按路径长度递增的顺序产生最短路径。通过以上对问题的分析和任务的理解，设计出一个大体的模块和程序流程。1程序中涉及到的结构体及子函数：1.1结构体：本程序设计使用了以下结构体：structvertexintnum;顶点编号intdata;顶点信息;顶点类型typedefstructgraphintn;图中顶点个数inte;图中边的个数structvertexvex

3、sMAXVEX;顶点集合intedgesMAXVEXMAXVEX;边的集合AdjMaxix;图的邻接矩阵类型1.2子函数：设计本程序需分成几个模块，要用到以下几个子函数：AdjMaxixcreatmgraph()/通过用户交互产生一个有向图的邻接矩阵；voiddispmgraph(AdjMaxixadj)/用于输出一个有向图的邻接矩阵；voidppath(intpath,inti,intv0)；选择输出一条最短路径voidDisPath(intdist,intpath,ints,intn,intvO)用path计算最短路径voidDijkstra(AdjMaxixg,intvO)/Dijkst

4、ra算法voidchange(intnum)用于替换顶点编号1.3结构图与流程图图2程序流程图、详细设计和编码这里设计用邻接矩阵解决实际生活中城市间往返最短路径问题。1算法思想把图中顶点集合分成两组，第一组为集合，存放已求出其最短路径的顶点，第二组为尚未确定最短路径的顶点集合是(用表示)，其中为网中所有顶点集合。在这里我们设计一个有向图G=(V,E)为G地区的交通图。1.1在这个图中，V=(1,2,邻邻N)代表各个城市oedges是表示G的邻接矩阵，edgesIj表示有向边vi,j的权，这里的权值代表城市间距离。若不存在有向边vi,j的权，则edgesIj的权为无穷大(可取值为INF=3257

5、0)设S为一个集合，其中的每个元素表示一个城市，求出从源点(自定义)城市到这些顶点城市的最短距离。S的初态只包含顶点V0o数组dist记录从V0到其他各城市当前的最短距离，其初值distI=edgesVOIo从S之外的顶点集合V-S中选出一个城市Uo使distw的值最小。于是从源点到达u只通过S中的城市，把u加入集合S中调整dist中记录的从源点到V-S中每个城市V的距离：从原来的distv和distw+edgeswv中选择较小的值作为新的distv。重复上述过程，直到S中包含V中其余顶点的最短路径。1.2算法描述：voidDijkstra(AdjMaxixg,intvO)intdistMAX

6、VEX,pathMAXVEX;intsMAXVEX;intmindis,i,j,u,n=g.n;for(i=0;ivn;i+)disti=g.edgesvOi;si=0；if(g.edgesvOivINF)pathi=vO;elsepathi=-1;sv0=1;pathv0=0;for(i=0;ivn;i+)mindis=INF;u=-1;for(j=0;jvn;j+)if(sj=O&distjvmindis)u=j;mindis=distj;su=1;for(j=O;jvn;j+)if(sj=0)if(g.edgesujvINF&distu+g.edgesujvdistj)distj=dis

7、tu+g.edgesuj;pathj=u;2采用邻接矩阵的存储结构2.1图的邻接矩阵可以使用一个二维数组存储顶点之间相邻关系的邻接矩阵，和一个具有N个元素的一维数组存储顶点信息，其中下标为i的元素存储顶点Vi的信息。2.2算法描述：voidCreatdl(vexlistGV,adjmatrixGA,intn,inte)intI,j,k,w;coutvv输入vvnvv个顶点GVI;for(I=0;Ivn;I+)for(j=o;jvn;j+)if(I=j)GAIj=o;elseGAIj=MaxValue;coutvv输入vvevv条边vvendl;for(k=1;kv=e;k+)cinIjw;GA

8、Ij=GAIj=w;四、上机调试对设计实现的回顾讨论和分析；算法的时、空性能分析和改进设想，经验和体会等。调试中遇到的问题与解决方法在进行输入输出语句的调试时，系统提示无法识别函数，缺少头文件viostream.h;出现重大错误，多达数百条错误，着实郁闷了一阵；很多标点符号是在中文输入法状态下输入，造成系统无法识别，改掉后错误消失；如switch语句，在每条选择语句后，缺少break。，错误；函数方法使用有误，无法通过；在赋实参时，对于变化的实参只需赋初值，子函数也可以调用子函数；困惑很久的调用子函数问题，在赋实参时找不到实参;用switch语句进行相关选择代换，成功。1.5连系实际问题上，i

9、nt型与char型的替换上不知道用什么函数实现；2设计体会对C语言的使用不是很熟练，造成自己浪费很多时间在复习C语言，女口：结构体的使用，不能灵活应用do,while()，switch()语句等；调用子函数问题上，子函数之间错综复杂的调用和实参，形参的赋值让自己很是迷惑，三天时间，也许更多时间里，都是在研究怎样调用子函数。虽然最后基本是完成了教授布置下来的课程设计，但是还是有不尽人意的地方：结点的插入，删除，路径的实际化最终由于时间问题没能解决，很遗憾。程序缺乏人性化设计，估计第一次使用本程序的人会很迷茫。3时间空间复杂度的计算利用算法求解最短路径时，求每一对顶点之间的最短路径的一种方法是反复

10、执行次算法每次执行以一个顶点为源点求得从该顶点到其它各顶点的最短路径其时间复杂度为。其空间的复杂度为o（n）。五、用户使用说明本程序主要是用来计算从某一点到其他各点的最短路径长度，第一次使用可能会有点迷茫，但是它却是本人两周来的血汗，如有不便请原谅。下面描述该使用方法：程序会在一开始让用户输入结点数，线路数，然后输入相关结点信息，有城市名字（只能使用英文名称），线路长度，起点城市，终点城市。接下来都由计算机完成。结果会输出源点到各城市间的长度。六、测试结果输入数据：输入城市数为：4输入城市线路为：4然后输入城市信息（这里每个数字彳弋表1A地2B地3C地4D地）:输入第一个城市信息：1输入第一个

11、城市信息：2输入第二个城市信息：3输入第四个城市信息：4输入第一条线路的起点：1，终点：3线路长度为KM：56输入第二条线路的起点：2，终点：3线路长度为KM：78输入第三条线路的起点：1，终点：2线路长度为KM：89输入第三条线路的起点：3，终点：4线路长度为KM：99F面是结果截图:F直每个数字代表一个城市，请输入相应的代码，第一个输入的是出发地I-7.Jrre二.右亠134-4:也也必自心息息息BitHf:4曙B:乍乍朋乍也也鞋煨讀；rGj入入入一皆釘干谒点点65X?nABC不的的的葩一一一:0一_-r7+-.一thmir药勻0一5555迪迪迪g*C:DocuentsandSetting

12、suserJ面YDetmgAhs!.eze谢谢使用加R路径查订系统，如果想退已请输入，护,任意犍继续:七、参考书目1徐孝凯数据结构实用教程，清华大学出版社，1999年12月第1版。2谭浩强c语言程序设计，清华大学出版社。3李春葆数据结构习题与解析，清华大学出版社，2004年2月第2版。4数据结构-C+语言描述，人民邮电出版社，2005年三月第1版。5数据结构（C语言描述），清华大学出版社，2004年十月第1版。八、附录：带注释的源程序*/*/*用Dijkstra算法求出有向图中某个源点到其他各顶点的最短路径长度*/*/*/*/*#includevstdio.h#includevmalloc.h

13、#includeviostream.h#includevstdlib.h#defineINF32767#defineMAXVEX100#defineMAX12structvertexintnum;intdata;；typedefstructgraphintn;inte;structvertexvexsMAXVEX;顶点编号顶点的信息顶点类型图中顶点的个数和边的个数顶点集合图的邻接矩阵类型通过用户交互产生一个有向图的邻接矩阵对图的所有信息进行逐步输入intedgesMAXVEXMAXVEX;边的集合AdjMaxix;AdjMaxixcreatmgraph()inti,j,k,w,n,e;intb

14、,t;AdjMaxixadj;coutvv输入城市数:;cinn;while(nMAX|nvO)coutvv城市个数不正确!请重新输入!vvendl;cinn;coutvv输入城市线路数:；cine;adj.n=n;adj.e=e;coutvv输入城市信息:n;for(i=0;ivn;i+)coutvv第vvi+1vv个城市的信息:；cinadj.vexsi.data;adj.vexsi.num=i;for(i=0;ivn;i+)for(j=0;jvn;j+)adj.edgesij=0;for(k=0;kve;k+)coutvv第vvk+1vv条线路:vvendl;coutvv起点:；cinb

15、;coutvv终点:；cint;coutvv线路长度为(Km):;cinw;i=0;while(ivn&adj.vexsi.data!=b)i+;if(i=n)coutvv输入的起点城市不存在!n;abort();j=0;while(jvn&adj.vexsj.data!=t)j+;if(j=n)coutvv输入的终点不存在!n;abort();adj.edgesij=w;return(adj);voiddispmgraph(AdjMaxixadj)/用于输出一个有向图的邻接矩阵inti,j,n,e;n=adj.n;e=adj.e;coutvv输出线路的矩阵表示:vvendl;coutvv;f

16、or(i=-1;ivn;i+)printf(%6d,i);printf(n);coutvvendl;for(i=0;ivn;i+)printf(%6d,i);for(j=0;jvn;j+)if(adj.edgesij=O)printf(%6s,“)；elseprintf(%6d,adj.edgesij);coutvvendl;voidppath(intpath,inti,intvO)intk;k=pathi;if(k=vO)return;ppath(path,k,vO);printf(%d,k);voidDisPath(intdist,intpath,ints,intn,intvO)inti;

17、printf(path:);for(i=O;ivn;i+)printf(%3d,pathi);printf(n);for(i=O;ivn;i+)if(si=1&i!=vO)用path计算最短路径输出path值用于输出最短路径和路径长度printf（从4到4的最短路径为:,vO,i）;printf(%d,vO);ppath(path,i,vO);printf(%dn,i);elseprintf（从4到4不存在路径n,vO,i）;voidDijkstra(AdjMaxixg,intvO)intdistMAXVEX,pathMAXVEX;intsMAXVEX;intmindis,i,j,u,n=g.

18、n;for(i=0;in;i+)disti=g.edgesvOi;si=0;if(g.edgesvOivINF)pathi=v0;elsepathi=-1;svO=1;pathvO=O;for(i=0;ivn;i+)mindis=INF;u=-1;距离初始化s置空路径初始化源点编号vO放入s中循环直到所有顶点的最短路径都求出选取不在s中且具有最小距离的顶点ufor(j=0;jvn;j+)if(sj=O&distjvmindis)u=j;mindis=distj;su=1;顶点u加入s中for(j=O;jvn;j+)修改不在s中的顶点的距离if(sj=0)if(g.edgesujvINF&distu+g.edgesujvdistj)distj=distu+g.edgesuj;pathj=u;printf(输出最短路径:n);DisPath(dist,path,s,n,v0);voidchange(intnum)switch(num)case1:printf(A地);break;case2:printf(B地);break;case3:printf(C地);b