数据结构课程设计报告 迪杰斯特拉算法的实现.docx

1、数据结构课程设计报告 迪杰斯特拉算法的实现数据结构课程设计报告迪杰斯特拉算法的实现班级：软件1408学号：1130505140825姓名：马宏伟指导教师：石老师完成时间：2012年7月5日题目:Dijkstra算法的实现一、 问题分析和任务定义1.1题 目：对任意图，选择合适的数据结构表示图，在此基础上实现求解最短路径的Dijkstra算法。1.2 要 求：对所设计的图的数据结构，提供必要的基本功能。1.3具体任务：建立图的表示模块，顶点的插入和删除操作模块；在建立图之后从单源点开始求最短路径，并显示出最短路径长度及路径途径！2、实现功能： 2.1建立有向图 2.2在建立好的有向图中，显示出来

2、从源点到其他各个顶点的最短路径长度及路径途径。3、测试用例： 3.1正确数据：a）顶点：3；边值信息：0 1 2；1 0 3；1 2 5；2 1 6；0 0 0； b）顶点：0；边值信息：0 0 0； 3.2错误数据：a）顶点：#； b）顶点：3；边值信息：0 1 #； 3.3参考用图：图1图1. 有向图问题分析: 题目要求选择合适的数据结构表示图，本程序邻接矩阵存储结点和弧等图的有关信息对用邻接矩阵表示的有向图，从某一顶点出发(称为源点)到该图其他各顶点(称为终点)有无路径？最短路径是什么？路径长为多少？问题要求写一个程序从有向网中的某一顶点出发找出该顶点到其余各顶点的最短路径。对邻接矩阵a

3、rscnn中的每一个元素只能有三种情况： 当顶点i到j无边时，distancej= MAX; 当顶点i到j 有边且权值为edgesij时，distancej= edgesij;当顶点i到就经过t有最短路径时，distancej=distancet+edgestj; 由于题目中没有规定输出格式，本程序以顶点序号的形式将最短路径输出到终端上去，并输出该最短路径的长度及路径途径。二、数据结构的选择和概要设计1) 数据存储结构以邻接矩阵存储有向图，如图2中有向图G所示，其邻接矩阵为图 3 edges。 图2. 有向图 图3.矩阵edges有向图的邻接矩阵arcsij定义为int edgesMAX_VE

4、RTEX_NUM MAX_VERTEX_NUM; 2)概要设计对用邻接矩阵表示的有向图，从某一顶点出发(称为源点)到该图其他各顶点(称为终点)有无路径？最短路径是什么？路径长为多少？问题要求写一个程序从有向网中的某一顶点出发找出该顶点到其余各顶点的最短路径。对邻接矩阵edgesMAX_VERTEX_NUM MAX_VERTEX_NUM中的每一个元素只能有三种情况：当顶点i到j无边时，distance= MAX; 当顶点i到j 有边且权值为edgesMAX_VERTEX_NUMMAX_VERTEX_NUM时，distancej= edgesMAX_VERTEX_NUM MAX_VERTEX_NU

5、M. 当顶点i到就经过t有最短路径时，distancej=distancet+edgestj;建立图的表示模块，顶点的插入和删除操作模块；在建立图之后从单源点开始求最短路径，并显示出来！流程图如图4图4.程序流程图（2) 设计表示法 (1) 函数调用关系如图下图所示。 (2) 函数接口说明。 void shortpath_DIJ(MGraph *mg,char i)VERTEX vexsMAX_VERTEX_NUM; int edgesMAX_VERTEX_NUMMAX_VERTEX_NUM; char pathMAX_VERTEX_NUMMAX_VERTEX_NUM; int distanc

6、eMAX_VERTEX_NUM; /* 求n个顶点，邻接矩阵为edges，从源点i到各顶点的最短路径，distance 记载从源点到其余各顶点的最短路径长度, path 为最短路径途径, 数组vexs用来存储顶点， (3)各部分的函数和各函数之间的关系采用邻接矩阵表示法，构造有向图typedef struct VERTEX /定义顶点类型typedef struct MGraph /定义图的类型MGraph *create_MGraph() /采用邻接矩阵创建有向图void shortpath_DIJ(MGraph *mg,char i) 用Dijkstra算法求有向图的mg的i顶点到其余顶点

7、的最短路径void main() (4) 实现注释(1) 系统限定邻接矩阵的阶n不超过max；(2) 为方便起见，系统假设有向网中边的权为整型数；(3) 若有向网中顶点i到j之间无边，则取值max。Dijkstra算法描述如下： (1) 输入顶点个数n，邻接矩阵edges和源点序号i。 (2) 送初值：将i加入第一组si=0；令distancej=edgesij;(j=0,1,2,n-1) (3) 重复n-1次做: 在不属于s的顶点U中，选取具有最小distancej值的顶点V； 将V加入s； 对不属于s的顶点j做 distancej=mindistancej;diatancet+edgest

8、j; /*distancej取(distancej,distancet+arcstj)两个数中的最小值 */ (4) 输出各最短路径的长度distancej及相应的最短路径pathj。3、详细设计和编码详细设计：1） 结点类型和指针类型typedef struct /定义顶点类型 int num; /顶点序号 char data; /顶点信息VERTEX;typedef struct /定义图的类型 int n; /顶点数目 int e; /弧的数目 VERTEX vexsMAX_VERTEX_NUM; /一维数组，存储顶点 int edgesMAX_VERTEX_NUMMAX_VERTEX_

9、NUM; /二维数组，存储边或弧MGraph;2） 采用数组(邻接矩阵)表示法，构造有向网mg的基本算法MGraph *create_MGraph() int i,j,k,w,n,e; char c; MGraph mg1,*mg=&mg1; printf(*请输入图的顶点数:*ntt); /读入顶点个数 scanf(%d,&n); printf(*请输入图中弧的数目:*ntt); /读入弧个数 scanf(%d,&e); mg-n=n; mg-e=e; getchar(); printf(n*输入顶点信息：*n); /读入第i个顶点信息 for(i=0;ivexsi.data=c; mg-v

10、exsi.num=i; /指定顶点的序号 for(i=0;in;i+) for(j=0;jedgesij=max; /先把所以的边置空 printf(请输入弧的信息，包括两个顶点及弧的权值：n); for(i=0;iedgesjk=w; return (mg); 3） 主要算法基本思想。单源最短路径问题采用迪杰斯特拉(Dijkstra)提出的按路径长度递增的次序产生最短路径的算法。此算法把网中所有的顶点分成两组，分别用s和U-s表示。凡是以i为源点，已经确定了最短路径的终点属于s，s的初态应只包含i。另一组U-s则是尚未确定最短路径的顶点集合。U-s的初态应是除源点外的网中所有顶点的集合，按各

11、顶点与i间的最短路径长度递增的次序，逐个把U-s中的顶点加入到s中，使得从i到s中各顶点的路径长度始终不大于从i到U-s中各顶点的路径长度。它的初始状态即是邻接矩阵edges中第i行内各列的值。显然，从源点到各顶点的最短路径中最短的一条路径应为distancej=mindistancej (j=0,1，2，n-1) 第一次求的最短路径必然是(i，j)，这时顶点号j应从U-s中删除而并入s。每当选出一个顶点号j并使之并入s后，就要修改U-s中各顶点的最短路径长度distance。对于U-s中的某一个顶点j来说，其最短路径长度或者仍是(i，j)，或者是(i，t，j)，决不可能有其他选择，也就是说，

12、若distancet+edgestjedgesij则修改distancej，使distancej= distancet+edgestj 当U-s组中各顶点的distance 进行修改后，再从中挑选出一个路径长度路径最小的顶点，从U-s中删除后再并入s。依次类推，就能求出所需的最短路径长度。 其中distance、U、s都定义为整型数组，数组s用以标记那些已经找到最短路径的顶点，若sj为1表示已找到源点到顶点j的最短路径；若sj为0，则表示从源点到顶点j的最短路径尚未求得。用Dijkstra算法求有向图的mg的i顶点到其余顶点j的最短路径Dijkstra算法描述如下： (1) 输入顶点个数n，邻

13、接矩阵edges和源点序号i。 (2) 送初值：将i加入第一组si=0；令distancej=edgesij;(j=0,1,2,n-1) (3) 重复n-1次做: 在不属于s的顶点U中，选取具有最小distancej值的顶点V； 将V加入s； 对不属于s的顶点j做 distancej=mindistancej;diatancet+edgestj; /*distancej取(distancej,distancet+arcstj)两个数中的最小值 */ (4) 输出各最短路径的长度distancej及相应的最短路径pathj。4、上机调试在调试过程中要特别注意函数调用时参数的传递问题，用数组名作为

14、参数可进行传值调用，因而可将函数中的运行结果传递给主调函数，得出正确结果；再一个要注意的是输出结果时，循环结束的条件应为：i=#时退出循环。另外，上机前的静态检查不能忽视；程序的调试过程可暂时多加一些输出语句以便及时查看一下中间运行情况，并对程序规格说明作少量调整和改动。算法的时间和空间性能分析1时间复杂度对于n个顶点的图，求一个顶点到其他顶点的最短路径，循环一次，加上修改最短路径的循环，是二层循环，所以，时间复杂度是O（n2）。2空间复杂度 因为这个程序旨在求出最短路径，但是必然要涉及到图的存储，而对于Dijkstra算法弄清楚两个顶点之间的关系又显得尤为重要，所以，面对图的几种存储结构，用

15、邻接表是比较合适的，不过它的缺点是占用空间大，复杂度为O（n2+m*n)。5、测试结果及其分析执行情况如下：输入：5 3 /*顶点个数为5，弧数为3*/ 0 1 2 3 4 /*顶点信息*/ 0 1 20 2 31 2 1 /* 输入有向网中带权值的边及权值 */0 /*源点为0*/1 /*源点为1*/# /*结束符*/结果如图5所示。6、用户使用说明程序执行后，首先输出：“输入图的顶点数：”输入图的顶点数后，输出：“输入输入图中弧的数目：”输入输入图中弧的数目后，输出：“输入顶点信息：”输入顶点信息后，输出：“请输入弧的信息，包括两个顶点及弧的权值：”（用空格键隔）输入弧的信息，包括两个顶点

16、及弧的权值后，输出：“请输入指定顶点i（输入#号结束）：”输入起始顶点名称之后，输出结果：图5.运行结果7、参考文献序号：ISBN 978-7-113-07628-3/TP.2201 作者：王昆仑 李红 书名：数据结构与算法 出版地：北京市宣武区右安门西街8号 出版社名称：中国铁道出版社 出版社年份20078、附录/Dijkstra算法实现#include iostream#include fstream#include string#include using namespace std;#define MAX_VERTEX_NUM 100 /顶点的最大个数#define max 65536

17、 /没有连接弧的顶点的距离typedef struct /定义顶点类型 int num; /顶点序号 char data; /顶点信息VERTEX;typedef struct /定义图的类型 int n; /顶点数目 int e; /弧的数目 VERTEX vexsMAX_VERTEX_NUM; /一维数组，存储顶点 int edgesMAX_VERTEX_NUMMAX_VERTEX_NUM; /二维数组，存储边或弧MGraph;MGraph *create_MGraph() int i,j,k,w,n,e; char c; MGraph mg1,*mg=&mg1; printf(*请输入图

18、的顶点数:*ntt); /读入顶点个数 scanf(%d,&n); printf(*请输入图中弧的数目:*ntt); /读入弧个数 scanf(%d,&e); mg-n=n; mg-e=e; getchar(); printf(n*输入顶点信息：*n); /读入第i个顶点信息 for(i=0;ivexsi.data=c; mg-vexsi.num=i; /指定顶点的序号 for(i=0;in;i+) for(j=0;jedgesij=max; /先把所以的边置空 printf(请输入弧的信息，包括两个顶点及弧的权值：n); for(i=0;iedgesjk=w; return (mg);voi

19、d shortpath_DIJ(MGraph *mg,char i) /图用邻居矩阵存储，i是源点 int inSMAX_VERTEX_NUM; /辅助数组用来标志顶点是否已经在 /最短路径的顶点集合中 char pathMAX_VERTEX_NUMMAX_VERTEX_NUM; /存放路径 int distanceMAX_VERTEX_NUM; /到源点的距离 int m,n,j,wm; int k=i-48; for(m=0;m(*mg).n;m+) /初始化各数组 inSm=0; distancem=(*mg).edgeskm; if(distancem%d,k,m); /将字符打入到字

20、符串中 inSk=1; /顶点i加入到集合s中 for(m=0;m(*mg).n-1;m+) /将最短路径顶点加入到s中 j=k;wm=max; for(n=0;n(*mg).n;n+) /找当前的最短路径 if(inSn=0&distancenwm) j=n;wm=distancen; inSj=1; /j顶点加入到s中 for(n=0;n(*mg).n;n+) /根据顶点调整当前的最短路径 if(inSn=0&distancej+(*mg).edgesjn%d,pathj,n); for(j=0;j(*mg).n;j+) if(distancej=max) printf(%d到%d的无路径

21、n,k,j); continue; else printf(%d到%d的最短路径为%d (%s)n,k,j,distancej,pathj); /*void main() MGraph mg1,*mg=&mg1; VERTEX v11,v22,v33,*v1=&v11,*v2=&v22,*v3=&v33; char i; mg=create_MGraph(); /图的创建 getchar(); printf(请输入指定顶点i(输入#号结束)：); /Djkstra法求最短路径 i=getch();while(i!=#) shortpath_DIJ(mg,i); printf(请输入指定顶点i(输入#号结束)：); /Djkstra法求最短路径 i=getch();