数据结构最短路径.doc

《数据结构最短路径.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、之间的最短路径。，用户可以自己输入各个地点及其之间的距离，便于用户在不同情况下均可使用。关键词：最短路径；Dijkstar；无向图;Word文档.目录目录1课题描述12需求分析13概要设计13.1存储结构13.2算法描述14详细设计14.1功能模块图14.2主函数14.3pd函数14.4CreateMGraph函数14.5Dijkstar函数15程序编码16程序的调试与测试18总结1参考文献11.目录中可以只有一级标题2.页码右侧对齐页边距3.本页不需要页码4.以上容仅作参考，具体章节由课程设计类型确定Word文档.Word文档.1课题描述随着交通的发展，人民生

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

4、用一个具有n个元素的一维数组存储顶点信息，其中下标为i的元素存储顶点vi的信息。因此，图的邻接矩阵的存储结构定义如下:#defineMVNum50typedefstruct{VertexTypevexs[MVNum];Adjmatrixarcs[MVNum][MVNum]；}Mgraph;图如下dacbeF图3.1无向图abcdefa∞34∞∞∞b3∞∞155∞c4∞∞312∞d∞153∞∞8e∞512∞∞6f∞∞∞86∞图2.1G的邻结矩阵Word文档.3.2算法描述(1)Dijkstra算法核心是贪心，实质是按路径长度递增产生诸顶点的最短路径算法。迪杰斯特拉

5、算法可用自然语言描述如下：初始化S和D,置空最短路径终点集，置初始的最短路径值；S[v1]=TRUE;D[v1]=0;While(S集中的顶点数

6、有一个源点，以后每求得一条最短路径，就将该路径的终点加入到集合S中）；第二组为其余待确定最短路径的顶点集合，用U表示。按最短路径长度的递增次序依次把U集合的顶点逐个加入到S集合中，约束条件是保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。算法的终止条件是集合U为空集，即集合U的顶点全部加入到集合S中。（4）Maxint：最大整数值，表示两个不能到达的顶点。Word文档.4详细设计4.1功能模块图如图4.1所示求最短路径Main函数Pd函数CreateMGraph函数图4.1功能模块4.2主函数主函数流程图如图4.2开始调用pd函

7、数调用CreateMGraph函数调用Dijkstar函数图4.2主函数Word文档.4.3pd函数函数如图4.3所示开始输入n，e（n是顶点数，e是边数）Nn>0&&e<=n(n-1)/2Y结束图4.3Pd函数Word文档.4.4CreateMGraph函数createMGraph函数如图4.4所示开始i=1i<=nNYG->vexs[i]=ii=i+1i=1Ni<=nYi=i+1j=1Nj<=nYG->arcs[i][j]=MaxintG->arcs[j][i]=Maxint无向图a<=>bj=j+1k=1Nj<=nYG->arcs[i][j]=Maxint

8、，G->arcs[j][