数据结构最短路径..docxVIP

数 据 结 构设计说明书单源点最短路径算法的实现学生姓名 王文刚 学 号 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 vexs[MVNum]; Adjmatrix arcs[MVNum][MVNum]；}Mgraph; 图如下dacbeF 图3.1 无向图a b c d e fa∞ 3 4 ∞ ∞ ∞b 3∞ ∞ 15 5 ∞c4∞ ∞ 3 12 ∞d∞ 15 3 ∞ ∞ 8e∞ 5 12 ∞ ∞ 6f∞ ∞ ∞ 8 6 ∞图2.1 G的邻结矩阵3.2 算法描述(1) Dijkstra算法核心是贪心，实质是按路径长度递增产生诸顶点的最短路径算法。迪杰斯特拉算法可用自然语言描述如下：初始化S和D,置空最短路径终点集，置初始的最短路径值；S[v1]=TRUE;D[v1]=0;While(S集中的顶点数n){ 开始循环，每次求的v1到某个v顶点的最短路径，并将v加到S集中; S[v]=TRUE; 更新当前最短路径及距离。}(2)Dijkstra算法结束后，通过设置一个数组记录下一个节点的前趋节点，然后通过倒叙的方式输出该最短路径。(3)Dijkstra算法思想为：设G=(V,E)，G是带权无向图，V代表图中顶点集合，E代表图中含权重的边集合。将全部顶点集合V分成两组，第一组为已求出最短路径的顶点集合，用S表示（初始时S中只有一个源点，以后每求得一条最短路径，就将该路径的终点加入到集合S中）；第二组为其余待确定最短路径的顶点集合，用U表示。按最短路径长度的递增次序依次把U集合的顶点逐个加入到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是边数）n0e=n(n-1)/2Y结束图4.3 Pd函数4.4 CreateMGraph函数createMGraph函数如图4.4所示开始i=1i=nYG-vexs[i]=ii=i+1i=1Ni=nYi=i+1j=1 Nj=nYG-arcs[i][j]=Maxint G-arcs[j][i]=Ma