大数据结构最短路径

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

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

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

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

4、的邻接矩阵表示，除了需要用一个二维数组存储顶点之间相邻关系的邻接矩阵外，通常还需要使用一个具有n个元素的一维数组存储顶点信息，其中下标为i的元素存储顶点vi的信息。因此，图的邻接矩阵的存储结构定义如下:#defineMVNum50typedefstruct{VertexTypevexs[MVNum];Adjmatrixarcs[MVNum][MVNum]；}Mgraph;图如下dac实用文档beF图3.1无向图abcdefa∞34∞∞∞b3∞∞155∞c4∞∞312∞d∞153∞∞8e∞512∞∞6f∞∞∞86∞图2.1G的邻结矩阵实用文档3

5、.2算法描述(1)Dijkstra算法核心是贪心，实质是按路径长度递增产生诸顶点的最短路径算法。迪杰斯特拉算法可用自然语言描述如下：初始化S和D,置空最短路径终点集，置初始的最短路径值；S[v1]=TRUE;D[v1]=0;While(S集中的顶点数

6、代表图中顶点集合，E代表图中含权重的边集合。将全部顶点集合V分成两组，第一组为已求出最短路径的顶点集合，用S表示（初始时S中只有一个源点，以后每求得一条最短路径，就将该路径的终点加入到集合S中）；第二组为其余待确定最短路径的顶点集合，用U表示。按最短路径长度的递增次序依次把U集合的顶点逐个加入到S集合中，约束条件是保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。算法的终止条件是集合U为空集，即集合U的顶点全部加入到集合S中。（4）Maxint：最大整数值，表示两个不能到达的顶点。实用文档4详细设计4.1功能模

7、块图如图4.1所示求最短路径实用文档Main函数Pd函数CreateMGraph函数图4.1功能模块4.2主函数主函数流程图如图4.2开始调用pd函数实用文档调用CreateMGraph函数调用Dijkstar函数图4.2主函数4.3pd函数函数如图4.3所示实用文档开始输入n，e（n是顶点数，e是边数）Nn>0&&e<=n(n-1)/2Y结束图4.3Pd函数实用文档实用文档4.4CreateMGraph函数createMGraph函数如图4.4所示开始i=1i<=nNYG->vexs[i]=ii=i+1i=1实用文档Ni<=nYi=i+1j

8、=1Nj<=nYG->arcs[i][j]=MaxintG->arcs[j][i]=Maxint无向图a<=>bj=j+1k=1Nj<=n实用文档YG->arcs[