求解最短路径的Dijkstra算法

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

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

3、 e;图中边的个数struct vertex vexsMAXVEX; 顶点集合int edgesMAXVEXMAXVEX; 边的集合AdjMaxix;图的邻接矩阵类型1.2子函数：设计本程序需分成几个模块，要用到以下几个子函数：AdjMaxix creatmgraph() 通过用户交互产生一个有向图的邻接矩阵；void dispmgraph(AdjMaxix adj)/用于输出一个有向图的邻接矩阵；void ppath(int path,int i,int v0)；选择输出一条最短路径void DisPath(int dist,int path,int s,int n,int v0)用path

4、计算最短路径void Dijkstra(AdjMaxix g,int v0) / Dijkstra 算法void change(int num)用于替换顶点编号、详细设计和编码这里设计用邻接矩阵解决实际生活中城市间往返最短路径问题。1算法思想把图中顶点集合分成两组，第一组为集合S，存放已求出其最短路径的顶点，第二组为 尚未确定最短路径的顶点集合是V-S (用U表示)，其中V为网中所有顶点集合。在这里我 们设计一个有向图G=(V，E)为G地区的交通图。1.1在这个图中，V= (1，2, ，N)代表各个城市。edges是表示G的邻接矩阵，edgesIj 表示有向边的权，这里的权值代表城市间距离。若

5、不存在有向边 的权，则 edgesIj的权为无穷大(可取值为INF=32570)。设S为一个集合，其中的每个元素表示 一个城市，求出从源点(自定义)城市到这些顶点城市的最短距离。S的初态只包含顶点 V0。数组dist记录从V0到其他各城市当前的最短距离，其初值distI=edgesV0I。从S 之外的顶点集合V-S中选出一个城市u。使distw的值最小。于是从源点到达u只通过S 中的城市，把u加入集合S中调整dist中记录的从源点到V-S中每个城市V的距离：从原 来的distv和distw+edgeswv中选择较小的值作为新的distv。重复上述过程，直到 S中包含V中其余顶点的最短路径。1.

6、2算法描述：void Dijkstra(AdjMaxix g,int v0)int distMAXVEX,pathMAXVEX;int sMAXVEX;int mindis,i,j,u,n=g.n;for(i=0;in;i+)disti=g.edgesv0i;si=0;if(g.edgesv0iINF)pathi=v0;elsepathi=-1;sv0=1;pathv0=0;for(i=0;in;i+)mindis=INF;u=-1;for(j=0;jn;j+)if(sj=0 & distjmindis)u=j;mindis=distj;su=1;for(j=0;jn;j+)if(sj=0)i

7、f(g.edgesujINF&distu+g.edgesujdistj)distj=distu+g.edgesuj; pathj=u;2采用邻接矩阵的存储结构2.1图的邻接矩阵可以使用一个二维数组存储顶点之间相邻关系的邻接矩阵，和一个具有N 个元素的一维数组存储顶点信息，其中下标为i的元素存储顶点Vi的信息。2.2算法描述：void Creatdl(vexlist Gadjmatrix GA,int n,int e)int I,j,k,w;cout”输入门个顶点 ”endlfor(I=0;IGVI;for(I=0;In;I+)for(j=o;jn;j+)if(I=j)GAIj=o;elseGA

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

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

10、用本程序的人会很迷茫。3时间空间复杂度的计算利用Dijkstra算法求解最短路径时，求每一对顶点之间的最短路径的一种方法是反复执行 n次Dijkstra算法，每次执行以一个顶点为源点，求得从该顶点到其它各顶点的最短路径； 其时间复杂度为O(n3)。其空间的复杂度为o(n)。五、用户使用说明本程序主要是用来计算从某一点到其他各点的最短路径长度，第一次使用可能会有点迷 茫，但是它却是本人两周来的血汗，如有不便请原谅。下面描述该使用方法：程序会在一开 始让用户输入结点数，线路数，然后输入相关结点信息，有城市名字(只能使用英文名称)， 线路长度，起点城市，终点城市。接下来都由计算机完成。结果会输出源点

11、到各城市间的长 度。六、测试结果输入数据：输入城市数为：4输入城市线路为：4然后输入城市信息(这里每个数字代表1 A地2 B地3 C地4 D地):输入第一个城市信息：1 输入第一个城市信息：2 输入第二个城市信息：3 输入第四个城市信息：4 输入第一条线路的起点：1，终点：3线路长度为KM：56输入第二条线路的起点：2，终点：3线路长度为KM：78输入第二条线路的起点：1，终点：2线路长度为KM：89输入第二条线路的起点：3，终点：4线路长度为KM：99下面是结果截图:c：,- *C: DocuAent s and Sett ingsuser桌面Debugks. exeF面每个数字代表一个城市

12、，请输入相应的代码，第一个输入的是出发弛也也 小飞 苣JL.也也 小飞 苣JL.巨JI-.巨JI-.巨JI- 时Hi:4r5信信信信 2矗善 也也城城城 AtGt入入入4 D地5 E地6 F地10 J弛 11 Kt也 12 L 设一条.图3输入所有城市信息图3输入所有城市信息0：,- *C: DocuAent s and Sett ingsuser桌面Debugks. exe输出线路的矩阵表示：-101230 12 38 8 8 8径 在短短短各地地地地路。首取到油BCD短不的的的地一一一 一最发一输 A-.fl:.fl:3路路路路地890 12 38 8 8 8径 在短短短各地地地地路。首取

13、到油BCD短不的的的地一一一 一最发一输 A-.fl:.fl:3路路路路地898 8 856788 88 8998,3,3,3程:0:0:0咯短Km01 2 3 3 3若长度为。则表示无法到达或在本地=谢谢使用H叫路径查讯系统，如果想退出请输入，任意键继续:图4输出最短路径七、参考书目1徐孝凯数据结构实用教程，清华大学出版社，1999年12月第1版。2谭浩强c语言程序设计，清华大学出版社。3李春葆数据结构习题与解析，清华大学出版社，2004年2月第2版。4数据结构-C+语言描述，人民邮电出版社，2005年三月第1版。5数据结构（C语言描述），清华大学出版社，2004年十月第1版。八、附录：带注

14、释的源程序 TOC o 1-5 h z /*/*/*用Dijkstra算法求出有向图中某个源点到其他各顶点的最短路径长度*/*/*/#include #include #include #include #define INF 32767#define MAXVEX 100#define MAX 12 struct vertex顶点编号顶点的信息顶点编号顶点的信息顶点类型int data;typedef struct graphint n;图中顶点的个数和边的个数int e;图中顶点的个数和边的个数struct vertex vexsMAXVEX;顶点集合int edgesMAXVEXMAXV

15、EX; 边的集合图的邻接矩阵类型通过用户交互产生一个有向图的邻接矩阵图的邻接矩阵类型通过用户交互产生一个有向图的邻接矩阵AdjMaxix creatmgraph()int i,j,k,w,n,e;int b,t;AdjMaxix adj;对图的所有信息进行逐步输入coutn;while(nMAX|n0)cout城市个数不正确!请重新输入!”n;coute;adj.n=n;adj.e=e;cout输入城市信息:n;for(i=0;in;i+)cout第i+1adj.vexsi.data;adj.vexsi.num=i;for(i=0;in;i+)for(j=0;jn;j+)adj.edgesij

16、=0;for(k=0;ke;k+)cout第k+1”条线路:endl;coutb;coutt;coutw;i=0;while(i=n)cout输入的起点城市不存在!n”;abort();j=0;while(j=n)cout输入的终点不存在!n”;abort();adj.edgesij=w;return(adj);void dispmgraph(AdjMaxix adj)/用于输出一个有向图的邻接矩阵 int i,j,n,e; n=adj.n;e=adj.e;cout输出线路的矩阵表示:endl;cout;for(i=-1;in;i+)printf(%6d,i);printf(n);couten

17、dl;for(i=0;in;i+)printf(%6d,i);for(j=0;jn;j+)if(adj.edgesij=0)printf(%6s”,8”)；elseprintf(%6d,adj.edgesij); coutendl;void ppath(int path,int i,int v0)int k;k=pathi;if(k=v0)return;ppath(path,k,v0);printf(%d,k);void DisPath(int dist,int path,int s,int n,int v0)用path用path计算最短路径/输出path值printf( path:);for

18、(i=0;in;i+)printf(%3d,pathi);printf(n);用于输出最短路径和路径长度for(i=0;in;i+)用于输出最短路径和路径长度if(si=1 & i!=v0)printf(M%d到d的最短路径为巴v0,i);printf(%d,”,v0);ppath(path,i,v0);printf(%dn”,i);elseprintf(M%d 到d 不存在路径n,v0,i);void Dijkstra(AdjMaxix g,int v0)int distMAXVEX,pathMAXVEX;int sMAXVEX;int mindis,i,j,u,n=g.n;void Dij

19、kstra(AdjMaxix g,int v0)int distMAXVEX,pathMAXVEX;int sMAXVEX;int mindis,i,j,u,n=g.n;for(i=0;in;i+)disti=g.edgesv0i;si=0;if(g.edgesv0iINF)pathi=v0;elsepathi=-1;sv0=1;pathv0=0;for(i=0;in;i+)mindis=INF;u=-1;for(j=0;jn;j+)if(sj=0 & distjmindis)u=j;mindis=distj;su=1;for(j=0;jn;j+)if(sj=0)距离初始化/s置空路径初始化源点编号v0放入s中循环直到所有顶点的最短路径都求出选取不在s中且具有最小距离的顶点u顶点u加入s中修改不在s中的顶点的距离if(g.edgesujINF & distu+g.edgesujdistj)distj=distu+g.edgesuj;pathj=u;printf(输出最短路径:n);DisPath(dist,path,s,n,v0);输出最短路径void change(int num)选择语句用于替换顶点值，输出名称switch(num)case 1: printf(A 地);break;case 2: printf(B 地);break;case 3:printf(C