资源描述：
《数据结构与算法基础报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、《数据结构与算法基础》课程项目实施总结报告题目：校园最短路径漫游组号：110任课教师：朱晓强组长：13121085支姜茏0.2组员：13121570汪舒雯0.2组员：13122979胡斌0.2组员：13121843刘鑫0.2组员：13122777王佑磊0.22015年10月18日目录一、项目要求1.项目名称2.项目要求3.项目介绍二、整体思路三、分部介绍1.Floyd算法程序部分1.1核心思路1.1.1路径矩阵1.1.2状态转移方程1.2算法过程1.3复杂度1.4算法描述1.5算法详情2.网页与数据部分2.1网页显示2.2数据库3.控制程序部分三、总结一、项目要求1、项目名称：校园最短路径漫游
2、2、项目要求根据校园各主要生活、学习、活动等场所、地点，设计并实现基于校园各场所之间的最短路径漫游。设计要求：（1）掌握数据结构的输入/输出；（2）设计与实现校园各主要场所之间的最短路径算法；（3）根据场所之间的最短路径及不同场所之间的路况信息，设置相应的步行、骑行等出行方式，计算到达每一目的地的时间及总的路程耗时；（4）各主要场所、地点以及漫游状态，以地图缩、放方式动态展示；（5）校园各主要场所、地点不少于50个。3、项目介绍评分依据：（1）功能实现；（2）性能指标；（3）工程规范（规范、安全性、可靠性、性价比等）；（4）理论水平；（5）团队分工合作情况。使用语言：JAVA,H5二、整体思路
3、将地图背景存于网页之中并建立坐标，将目标点与路径存入，调用算法计算得出所求返回到网页显示出所求。实现方案：采用java做后台，H5的Canvar作为结果展示部分。总体架构：springMvc+hibernate+html5+jquery。三、分部介绍本项目总体分为三个部分：Floyd算法程序，网页与数据，总控制程序。1、Floyd算法程序部分1.1核心思路1.1.1路径矩阵通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。从图的带权邻接矩阵A=[a(i,j)]n×n开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；……；最
4、后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。采用松弛技术（松弛操作），对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为O(n^3)。1.1.2状态转移方程其状态转移方程如下：map[i,j]:=min{map[i,k]+map[k,j],map[i,j]}；map[i,j]表示i到j的最短距离，K是穷举i,j的断点，map[n,n]初值应该为0，或者按照题目意思来做。当然，如果这条路没有通的话，还必须特殊处理，比如没有map[i,k
5、]这条路。1.2算法过程1，从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。2，对于每一对顶点u和v，看看是否存在一个顶点w使得从u到w再到v比已知的路径更短。如果是更新它。把图用邻接矩阵G表示出来，如果从Vi到Vj有路可达，则G[i,j]=d，d表示该路的长度；否则G[i,j]=无穷大。定义一个矩阵D用来记录所插入点的信息，D[i,j]表示从Vi到Vj需要经过的点，初始化D[i,j]=j。把各个顶点插入图中，比较插点后的距离与原来的距离，G[i,j]=min(G[i,j],G[i,k]+G[k,j])，如果G[i,j]的值变小，则D[i,j]=k。在
6、G中包含有两点之间最短道路的信息，而在D中则包含了最短通路径的信息。比如，要寻找从V5到V1的路径。根据D，假如D(5,1)=3则说明从V5到V1经过V3，路径为{V5,V3,V1}，如果D(5,3)=3，说明V5与V3直接相连，如果D(3,1)=1，说明V3与V1直接相连。1.3复杂度时间复杂度:O(n^3)；空间复杂度:O(n^2)1.4算法描述a) 初始化：D[u,v]=A[u,v]b) Fork:=1tonFori:=1tonForj:=1tonIfD[i,j]>D[i,k]+D[k,j]ThenD[i,j]:=D[i,k]+D[k,j];c) 算法结束：D即为所有点对的最短路径矩阵1
7、.5算法详情（见附录一）2、网页与数据部分2.1网页显示首先来看一下H5的画布：上图就是用canvar画出来的（画图的主要脚本函数见附录二）从百度地图截取地图作为网页的背景，并在网页中建立直角坐标系，标注各个坐标点作为所需目标点，再录入目标点之间的路径同时录入距离，此时所有所需数据经控制程序读取载入到Floyd算法中几科求得所需。（关于前台网页总程序见附录三）2.2数据库如上文所述，数据获取之后存
