数据结构最短路径

1、数 据 结 构设计说明书单源点最短路径算法的实现学生姓名 王文刚 学 号 1418064056 班 级 网络1402 成 绩 指导教师 数学与计算机科学学院年 月 日 课程设计任务书20 20 学年第 学期课程设计名称： 数据结构课程设计 课程设计题目： 单源点最短路径算法的实现 完 成 期 限：自 年 月 日至 年 月 日共 2 周设计内容：1.任务说明2.要求3.参考资料指导教师： 教研室负责人：课程设计评阅评语： 指导教师签名： 年 月 日摘 要设计了一求解最短路径的方法，该方法具有在输入的途中查找两个顶点之间的最短路径的功能。本方法采用VC+作为软件开发环境，采用Dijkstar函数来

2、求取顶点之间的最短路径。，用户可以自己输入各个地点及其之间的距离，便于用户在不同情况下均可使用。关键词：最短路径；Dijkstar；无向图;目 录目录1课题描述22 需求分析33概要设计43.1 存储结构43.2 算法描述54详细设计64.1 功能模块图64.2 主函数64.3 pd函数74.4 CreateMGraph函数84.5Dijkstar函数95程序编码116程序的调试与测试158总结16参考文献171.目录中可以只有一级标题2.页码右侧对齐页边距3.本页不需要页码4.以上内容仅作参考，具体章节由课程设计类型确定1课题描述 随着交通的发展，人民生活水平的提高。出门旅行变的越来越频繁，

3、而且供暖也成为冬天不可或缺的内容。为了节约时间和金钱，所以人们都希望找到旅行目的地的最短路径和架设暖气的最短路径。那么如何找到最短路径呢？由于路径较多，手工计算比较麻烦，而且容易出错，因此人们用计算机语言代替手工计算求最短路径。而在计算机语言中迪杰斯特拉算法比较常见，简洁，故人们常借助计算机程序迪杰斯特拉算法求最短路径。这样可以广泛提高效率，容易理解。2 需求分析3概要设计3.1 存储结构一个图的邻接矩阵表示是唯一的。图的邻接矩阵表示，除了需要用一个二维数组存储顶点之间相邻关系的邻接矩阵外，通常还需要使用一个具有n个元素的一维数组存储顶点信息，其中下标为i的元素存储顶点vi的信息。因此，图的邻

4、接矩阵的存储结构定义如下:#define MVNum 50typedef struct VertexType vexsMVNum; Adjmatrix arcsMVNumMVNum；Mgraph; 图如下dacbeF 图3.1 无向图a b c d e fa 3 4 b 3 15 5 c 4 3 12 d 15 3 8e 5 12 6f 8 6 图2.1 G的邻结矩阵3.2 算法描述(1) Dijkstra算法核心是贪心，实质是按路径长度递增产生诸顶点的最短路径算法。迪杰斯特拉算法可用自然语言描述如下：初始化S和D,置空最短路径终点集，置初始的最短路径值；Sv1=TRUE;Dv1=0;Whil

5、e(S集中的顶点数<n) 开始循环，每次求的v1到某个v顶点的最短路径，并将v加到S集中; Sv=TRUE; 更新当前最短路径及距离。(2)Dijkstra算法结束后，通过设置一个数组记录下一个节点的前趋节点，然后通过倒叙的方式输出该最短路径。(3)Dijkstra算法思想为：设G=(V,E)，G是带权无向图，V代表图中顶点集合，E代表图中含权重的边集合。将全部顶点集合V分成两组，第一组为已求出最短路径的顶点集合，用S表示（初始时S中只有一个源点，以后每求得一条最短路径，就将该路径的终点加入到集合S中）；第二组为其余待确定最短路径的顶点集合，用U表示。按最短路径长度的递增次序依次把U集合

6、的顶点逐个加入到S集合中，约束条件是保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。算法的终止条件是集合U为空集，即集合U的顶点全部加入到集合S中。（4）Maxint：最大整数值，表示两个不能到达的顶点。4详细设计4.1 功能模块图 如图4.1所示求最短路径 Main函数Pd函数CreateMGraph函数图4.1功能模块4.2 主函数 主函数流程图如图4.2开始 调用pd函数调用CreateMGraph函数调用Dijkstar函数 图4.2 主函数4.3 pd函数函数如图4.3所示开始输入n，e（n是顶点数，e是边数）Nn>0&&e&l

7、t;=n(n-1)/2Y结束图4.3 Pd函数4.4 CreateMGraph函数createMGraph函数如图4.4所示开始i=1i<=nNYG->vexsi=ii=i+1i=1Ni<=nYi=i+1j=1 Nj<=nYG->arcsij=Maxint G->arcsji=Maxint无向图a<=>bj=j+1k=1Nj<=nYG->arcsij=Maxint，G->arcsji=Maxint无向图a<=>b开始k=k+1图4.4 createMGraph函数4.5Dijkstar函数 开始v1到其余顶点集合v最

8、短路径,带权长度 DMVnum,PMVnumv=1Nv<=nY置空s Sv=FALSE,D2v=G.arcsv1v若权值小与最大值D2v<Maxint NYPv=0Pv=v1v=v+1初始化，v1顶点属于s集D2v1=0:sv1开始主循环，每次求得v1到某个v顶点的最短路径，并加到s中v=w,min=D2w if(!Sw&&D2w<min)Ni<=nY当前所知离v1顶点最近距离min=Maxint顶点变量 w=1Nw<=nYN!Sw&&D2w<min Yv=w w顶点离v1更近Sv=TRUE;w=1w=w+1Nw<=nY

9、(!Sw&&(D2v+G.arcsvw<D2w)N修改D2w，P2wD2w=D2v+G.arcsvw;P2w=vw=w+1i=i+1i=1i<=mY输出数据i=i+1结束5程序编码#include<stdio.h> #include<stdlib.h> #define MVNum 100 #define Maxint 32767 typedef char VertexType; typedef int Adjmatrix; typedef enum FALSE,TRUEboolean; typedef struct VertexType ve

10、xsMVNum; Adjmatrix arcsMVNumMVNum; MGraph; int D1MVNum,P1MVNum; int DMVNumMVNum,PMVNumMVNum; int pd(MGraph *G,int &n,int &e) while(n>0)&&(e>n*(n-1)/2)printf("你输入的顶点或边数不正确，请重新图中顶点个数和边数n，e:");scanf("%d,%d",&n,&e); return TRUE; CreateMGraph(MGraph *G,in

11、t n,int e) int i,j,k,w; char a,b; for(i=1;i<=n;i+) G->vexsi=i; for(i=1;i<=n;i+) for(j=1;j<=n;j+) G->arcsij=Maxint; G->arcsji=Maxint; printf("输入%d条边的i,j及w:n",e);for(k=1;k<=e;k+) fflush(stdin); scanf(" %c,%c,%d",&a,&b,&w); i=a-'a'+1; j=b-

12、9;a'+1; G->arcsij=w; G->arcsji=w; printf("无向图的存储结构建立完毕!n"); void Dijkstra(MGraph G,int v1,int n) int D2MVNum,P2MVNum; int v,i,w,min; boolean SMVNum; / 判断该点是否到过S中，即该点是否被遍历 for(v=1;v<=n;v+) Sv=FALSE; D2v=G.arcsv1v; if(D2v<Maxint) P2v=v1; else P2v=0; D2v1=0;Sv1=TRUE; for(i=2;i

13、<=n;i+) min=Maxint; for(w=1;w<=n;w+) if(!Sw&&D2w<min) v=w;min=D2w; Sv=TRUE; for(w=1;w<=n;w+) if(!Sw&&(D2v+G.arcsvw<D2w) D2w=D2v+G.arcsvw; P2w=v; printf("最短路径-路径n"); for(i=1;i<=n;i+) printf("%5d",D2i); printf("%14c",i-1+'a');v=P2

14、i; while(v!=0) printf("<-%c",v-1+'a'); v=P2v; printf("n"); void main() MGraph G; int n,e,v; char ch; printf("输入图中顶点个数和边数n，e:"); scanf("%d,%d",&n,&e); pd(&G,n,e);/scanf("%d,%d",&n,&e);/n=r;/e=a;CreateMGraph(&G,n,e);

15、while(1) printf("求最短路径，输入开始点v:"); fflush(stdin); scanf("%c",&ch); v=ch-'a'+1; Dijkstra(G,v,n); 6程序的调试与测试调试如图6.1所示 输入：2,5a,b,5a,c,15 b,c,6 b,d,2 c,d,10a b 图6.17总结本次课程设计涉及到的范围很广，让我能够比较系统的对C语言和数据结构进行一次整理和复习。同时有了很多的体会和经验。在这次课程设计中我体会到C语言超强的逻辑性，能够熟练使用的编译环境，也对这两门课程有了新的认识，他们既有联系，又相互区别，在编写程序过程中要灵活应用。一开始信息是不能重复查询也就是说，整个设计过程中，遇到了很多问题，例如查询一次后退出重新运行才可以不能连续查询后来添加了一个简单的while()语句就实现了二次查询这次“求解最优路径”的课题，让我明白很多不知道的知识内容，对求解最优路径有了进一步的了解和认识。最后感谢老师布置给我们的任务，我会更加努力的学好这方面的知识，编写出更有价值的程序。最短路径算法关键先把已知最短路径顶点集 (只有一个源点