数据结构最短路径.doc

_数 据 结 构设计说明书单源点最短路径算法的实现学生姓名 王文刚 学 号 1418064056 班 级 网络1402 成 绩 指导教师 数学与计算机科学学院年 月 日 精品资料课程设计任务书20 20 学年第 学期课程设计名称： 数据结构课程设计 课程设计题目： 单源点最短路径算法的实现 完 成 期 限：自 年 月 日至 年 月 日共 2 周设计内容：1.任务说明2.要求3.参考资料指导教师： 教研室负责人：课程设计评阅评语： 指导教师签名： 年 月 日摘 要设计了一求解最短路径的方法，该方法具有在输入的途中查找两个顶点之间的最短路径的功能。本方法采用VC+作为软件开发环境，采用Dijkstar函数来求取顶点之间的最短路径。，用户可以自己输入各个地点及其之间的距离，便于用户在不同情况下均可使用。关键词：最短路径；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课题描述 随着交通的发展，人民生活水平的提高。出门旅行变的越来越频繁，而且供暖也成为冬天不可或缺的内容。为了节约时间和金钱，所以人们都希望找到旅行目的地的最短路径和架设暖气的最短路径。那么如何找到最短路径呢？由于路径较多，手工计算比较麻烦，而且容易出错，因此人们用计算机语言代替手工计算求最短路径。而在计算机语言中迪杰斯特拉算法比较常见，简洁，故人们常借助计算机程序迪杰斯特拉算法求最短路径。这样可以广泛提高效率，容易理解。2 需求分析3概要设计3.1 存储结构一个图的邻接矩阵表示是唯一的。图的邻接矩阵表示，除了需要用一个二维数组存储顶点之间相邻关系的邻接矩阵外，通常还需要使用一个具有n个元素的一维数组存储顶点信息，其中下标为i的元素存储顶点vi的信息。因此，图的邻接矩阵的存储结构定义如下:#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;While(S集中的顶点数0&e=n(n-1)/2Y结束图4.3 Pd函数4.4 CreateMGraph函数createMGraph函数如图4.4所示开始i=1ivexsi=ii=i+1i=1Ni=nYi=i+1j=1 Njarcsij=Maxint G-arcsji=Maxint无向图abj=j+1k=1Njarcsij=Maxint，G-arcsji=Maxint无向图ab开始k=k+1图4.4 createMGraph函数4.5Dijkstar函数 开始v1到其余顶点集合v最短路径,带权长度 DMVnum,PMVnumv=1Nv=nY置空s Sv=FALSE,D2v=G.arcsv1v若权值小与最大值D2vMaxint NYPv=0Pv=v1v=v+1初始化，v1顶点属于s集D2v1=0:sv1开始主循环，每次求得v1到某个v顶点的最短路径，并加到s中v=w,min=D2w if(!Sw&D2wmin)Ni=nY当前所知离v1顶点最近距离min=Maxint顶点变量 w=1Nw=nYN!Sw&D2wmin Yv=w w顶点离v1更近Sv=TRUE;w=1w=w+1Nw=nY(!Sw&(D2v+G.arcsvwD2w)N修改D2w，P2wD2w=D2v+G.arcsvw;P2w=vw=w+1i=i+1i=1i=mY输出数据i=i+1结束5程序编码#include #include #define MVNum 100 #define Maxint 32767 typedef char VertexType; typedef int Adjmatrix; typedef enum FALSE,TRUEboolean; typedef struct VertexType vexsMVNum; Adjmatrix arcsMVNumMVNum; MGraph; int D1MVNum,P1MVNum; int DMVNumMVNum,PMVNumMVNum; int pd(MGraph *G,int &n,int &e) while(n0)&(en*(n-1)/2)printf(你输入的顶点或边数不正确，请重新图中顶点个数和边数n，e:);scanf(%d,%d,&n,&e); return TRUE; CreateMGraph(MGraph *G,int n,int e) int i,j,k,w; char a,b; for(i=1;ivexsi=i; for(i=1;i=n;i+) for(j=1;jarcsij=Maxint; G-arcsji=Maxint; printf(输入%d条边的i,j及w:n,e);for(k=1;karcsij=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(D2vMaxint) P2v=v1; else P2v=0; D2v1=0;Sv1=TRUE; for(i=2;i=n;i+) min=Maxint; for(w=1;w=n;w+) if(!Sw&D2wmin) v=w;min=D2w; Sv=TRUE; for(w=1;w=n;w+) if(!Sw&(D2v+G.arcsvwD2w) D2w=D2v+G.arcsvw; P2w=v; printf(最短路径-路径n); for(i=1;i=n;i+) printf(%5d,D2i); printf(%14c,i-1+a);v=P2i; 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); 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()语句就实现了二次查询这次“求解最优路径”的课题，让我明白很多不知道的知识内容，对求解最优路径有了进一步的了解和认识。最后感谢老师布置给我们的任务，我会更加努力的学好这方面的知识，编写出更有价值的程序。最短路径算法关键先把已知最短路径顶点集 (只有一个源点)和未知的顶点分开，然后依次把未知集合的顶点按照最短路径(这里特别强调一下是源点到该顶点的路径权重和，不仅仅是指它和父结点之间的权重，一开始就是在没有这个问题弄清楚)加入到已知结点集中。