82组终期报告数据结构与算法基础.doc

《数据结构与算法基础》课程项目 实施报告 题 目： 校园最短路径漫游 组 号： 任课教师： 组 长： 成 员： 成 员： 成 员： 成 员： 联系方式： 年 月 日 报告目录 课程项目实施方案 课程设计要求 设计思想 算法基础 软件基础 实现方式 6. 关键技术 二、项目的结果分析展示 三、项目总结以及对于数据结构与算法课程的感悟 四、项目分工 五、源程序代码及注释 一、课程项目实施方案 1.课程设计要求： 根据校园各主要生活、学习、活动等场所、地点，设计并实现基于校园各场所之间的最短路径漫游。 要求： （1）掌握数据结构的输入/输出； （2）设计与实现校园各主要场所之间的最短路径算法； （3）根据场所之间的最短路径及不同场所之间的路况信息，设置相应的步行、骑行等出行方式，计算到达每一目的地的时间及总的路程耗时； （4）各主要场所、地点以及漫游状态，以地图缩、放方式动态展示； （5）校园各主要场所、地点不少于50个。 2.设计思想： 具体分析： （1）.打开初始界面，直接输入起始点和终点，实现最短路径查询、校园场所的介绍等功能。 （2）.操作方式 I.最短路径查询：分别选择界面中“起始点”和“终点”的下拉框里的50个校园场所，点击“查询”按钮，会在界面上方的“最短路径”小框中出现最短路径的具体方案，以及大致的距离，同时在界面地图上以动画方式展现出具体的最短路径。如果起点和终点的场所选择相同，会出现“选择错误，您选择的起点与终点是相同的”的提示。 II．校园场所介绍：鼠标点击校园地图中50个场所之一，会在“校园介绍”中显示该场所名称以及可直达的校园地点。 （3）.结束最短路径查询之后，点击界面上的退出按钮从而退出界面。 根据对课程项目设计要求的分析，我们程序设计的流程图大致如下： 3.算法基础： 【Dijkstra算法】 1.定义概览 Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权边。 问题描述：在无向图 G=(V,E) 中，假设每条边 E[i] 的长度为 w[i]，找到由顶点 V0 到其余各点的最短路径。（单源最短路径） 2.算法描述 1)算法思想：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。 2)算法步骤： a.初始时，S只包含源点，即S＝{v}，v的距离为0。U包含除v外的其他顶点，即:U={其余顶点}，若v与U中顶点u有边，则u,v正常有权值，若u不是v的出边邻接点，则u,v权值为∞。 b.从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。 c.以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。 d.重复步骤b和c直到所有顶点都包含在S中。 3 代码 /*用迪杰斯特拉算法求有向网G的V0顶点到其他顶点的最短路径P，以及其带权长度D。其中P是二维数组，行号表示终点，列号表示经过的路径。P[v][w]为TRUE的意思就是从v0到v,要经过w点)。D是一维数组，表示某顶点到v0点的路径长(D[v] == 10表示从v0到v要经过的路径长度为10。final存放已经求得的路径结果(比如final[v]为TRUE表示已经找到v0到v的最短路径)。*/void? ShorttestPath_DIJ(? MGraph? G,? int? v0,? PathMatrix