毕业论文：计算机科学与技术.doc

《毕业论文：计算机科学与技术.doc》由会员分享，可在线阅读，更多相关《毕业论文：计算机科学与技术.doc（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1毕毕 业业 论论 文文题 目： 用 Floyd 算法实现对校园教学楼间的路径的计算 学 院： 计算机科学与工程学院 专 业： 计算机科学与技术 毕业年限： 学生姓名： 学 号： 指导教师： 2用 Floyd 算法计算校园教学楼间的路径摘要：摘要：最短路径是图论中的一个重要问题，具有很高的实用价值，在地图中寻找最佳路径就是其重要的价值之一。本文章通过个人的经验，草拟了一份师大个教学楼间的带权图，用邻接矩阵存储，并通过求解网络中任意两点之间最短路径的高效方法 Floyd 算法来实现查找从一个教学楼到另一个教学楼的最短有效路径，为了便于实际操作，并用 java 中的 swing 组件实现简单的图形

2、界面。关键字：Floyd 算法，邻接矩阵，最短路径,JavaSwing 组件编程，图的应用。目录1 西北师大教学楼的简单分布图.3 2 图的简介.4 2.1 图的基本概念.4 2.2 图的存储结构.4 2.2.1 邻接矩阵的数据类型.5 2.2.2 邻接矩阵存储方法.5 2.2.3 邻接矩阵的特点.6 3 最短路径算法的介绍.6 3.1 最短路径.6 3.1.1 最短路径的算法.6 3.1.2 Dijkstra 算法.7 3.1.3Floyd 算法.8 3.1.4 两种算法的比较.9 4 编程实现.10 4.1 编程语言的介绍.10 4.2 程序实现的流程图.10 4.3 程序源代码.11 4

3、.3.1 图形界面的的源代码。.11 4.3.2 最短路径算法的代码。.12 4.3.3运行程序.14 参考文献.15 5结束语.1631 1 西北师大教学楼的简单分布图西北师大教学楼的简单分布图下面是我画的师大一些重要的教学楼的分布图，如图 1-1图 1-1.西北师大教学楼的简单分布图2 图的简介图的简介2.12.1 图的基本概念图的基本概念图（Graph）由两个集合 V(vertex)和 E（edge）组成,记为 G = (V , E),其中，V 是定顶点的集合，记为 V(G)，E 是两个不同顶点（顶点对）边的有限集合，记为 E(G)。42.2 图的存储结构图的存储除了要存储个顶点本身的信

4、息外，还要存储定点与定点之间所有的关系（边的关系） ，图的存储结构一般有四种，分别是邻接矩阵、邻接表、十字邻接表存储、邻接多重表存储。由于用邻接矩阵存储有利于最短路径算法的实现，而且图中的定点数目有限，故本文章用邻接矩阵存储图中的信息。2.2.12.2.1 邻接矩阵的数据类型邻接矩阵的数据类型邻接矩阵的数据类型定义如下：define MAXV 99/最大顶点个数 Class VertexType int no;/顶点编号InfoType info;/顶点其他信息 ; public class MGraph int edgesMAXVMAXV;/邻接矩阵int n,e;/顶点数，弧数Vertex

5、Type vexsMAXV;/存放顶点信息 ；2.2.22.2.2 邻接矩阵存储方法邻接矩阵存储方法邻接矩阵是表示顶点之间相邻关系的矩阵。设 G= （V , E）是具有 n（n 0）个顶点的图，顶点的顺序依次为（v0,v1,.,vn-1）,则 G 的邻接矩阵 A 是 n 阶方阵，其定义如下：（1）如果 G 是无向图，则：Aij = 其他若 0E(G),(1vjvi（2） 如果 G 是有向图，则： 5Aij = 其他若 0E(G),1vjvi（3）如果 G 是带权无向图，则：Aij = 其他，且若vjvivjvivjviij0E(G),(w（4）如果 G 是带权有向图，则：Aij = 其他，且若

6、vjvivjvivjviij0E(G),w2.2.32.2.3 邻接矩阵的特点邻接矩阵的特点邻接矩阵的特点如下：邻接矩阵的表示是唯一的。无向图的邻接矩阵是一个对称矩阵，可以用压缩存储的方法存储。用邻接矩阵的方法存储图，要确定图中有多少边，则按行、按列对每个元素进行检测，所花费的时间代价很大, 但是很容易确定图中任意两点之间是否有边相连。3 3 最短路径算法的介绍最短路径算法的介绍3.13.1 最短路径最短路径3.1.13.1.1 最短路径的算法最短路径的算法在一个带权的图中，若从一个顶点到另一个顶点存在路径，则通常把一条路径上的权值之和定义为该路径上的长度或称为带权路径长度。从原点到终点可能不

7、止一条路径，把带权路径长度最短的那条路径称为最短路径，其路径长6度（权值之和）称为最短路径的长度或者最短距离。图的最短路径有两方面的问题：求图中一顶点到其他顶点的最短路径，可以用 Dijkstra 算法实现；求图中每一对定点之间的最短路径，实现方法有两种：一是分别以图中的每个顶点为源点共调用 n 次 Dijkstra 算法；另外还有一种算法：Floyd 算法。3.1.23.1.2 DijkstraDijkstra 算法算法Dijkstra 算法的基本思想为：设 G(V,E)是一个带权有向图，把图中的顶点集合分为两组，第一组为已求出最短路径的顶点集合（用 S 表示，初始时，S中只有一个初始点，以

8、后每求得一条最短路径 v, ,v ，就将 v 加入集合中知kk 道全部顶点加入 S 集合中，算法就结束了)，第二组为其余未确定最短路径的集合（用 U 表示） ，按最短路径长度的递增次序，将顶点加入 S 中。在向 S 中添加顶点式时，总保持从源点 v 到 S 中的个顶点中的最短路径长度不大于从源点到 U 中任何顶点最短路径的长度，例如，若向 S 中添加的顶点是 k,对于 U 中的内一个顶点 u，若顶点 k 到顶点 u 有边（权值为 w）,且原来ku 从顶点 v 到顶点 u 的长度（c）大于从顶点 v 到顶点顶点 k（c）与 w之和，vuvkku 即 c c + w，如图 3-1 所示，则将 v=

9、k=u 的路径作为新的最短路径。vuvkku 实际上，从顶点 v 到顶点 u 的这条新的最短路径是只包括 S 中的顶点为中间点的当前最短路径的长度，随着 S 中的顶点增加，当 S 包含所有顶点时，这条新的最短路径就是最终的最短路径kvu cvucvkwku7图 3-1 从顶点 v 到 u 的路径比较。Dijkstra 算法的具体步骤描述如下：步骤(1) 初始化： S = v(v 是源点)，distvi = i = (0, ,n-1)，其他，且若vjvivjvivjviij0E(G),wpathi = 其他有边时到当 1)iv(v步骤(2) w = minw , i,kS(把顶点 k 加入 S

10、中)。vkviU步骤(3) c c + w 则 c = c + w,pathu = k。Uuvuvkkuvuvkku步骤(4) 重复步骤(2)和步骤(3)，直到所有的顶点加入 S 中。3.1.33.1.3 FloydFloyd 算法算法Floyd 算法思想可用如下表达式描述：Ai,j = costi,j (假设图 G= (V,E)采用邻接矩阵 cost 存储)1 Ai,j = minA i,j，Ai,k+1 Ak+1,j(-1= Ai,jk1kA i.kkA k,jk图 3-2 若Ai,k+1 +Ai,k+1 flody(Integer dist) Integer path=new Integ

11、erdist.lengthdist.length;/存储的是从i-j经过的最后一个节点for (int i = 0; i (distik+ distkj) /修改路径pathij=k;/存储的是从i-j经过的最后一个节点distij=(distik + distkj); ArrayList list =new ArrayList();list.add(dist);list.add(path);return list;134.3.34.3.3运行程序运行程序（1）选择起点（2）选择终点鼠标单击鼠标单击选择起点14(3)查找路径参考文献参考文献1.李春葆. 数据结构教程.第二版.北京.清华大学出版

12、社.20072.Robert L.Kruse、Alexander J.Ryba .数据结构与程序设计.影印版.北京.高等教育出版社.20013.陈浩 等.Java 应用开发指南.珍藏版.北京.清华大学出版社4.谭浩强.C+程序设计.北京.清华大学出版社.20065.William.J.Collins.陈曙晖.数据结构和 Java 集合框架.北京.清华大学出版社6.李钟尉、陈丹丹.Java 开发实战 1200 例第二卷.北京.清华大学出版社.20117.郝自军 、何尚录.最短路问题的 Floyd 算法的若干讨论. 重庆工学院学报(自然科学). 2008.05选择终点鼠标单击查询结果155 5结束

13、语结束语毕业设计终于完成了，除了变得轻松和释然外，心里还有遗憾和失落，就像一个长跑运动员跑完了自己的赛程，是不是第一并不重要，关键是自己努力了，坚持下来了，自己终于跑到终点了。记得上次写学年论文时虽然很早就准备了，但由于第一次写论文设计，准备了一大堆东西，却很混乱，没条理，感谢老师的细心指导，通过多次修改完善包括代码设计和论文内容，还有论文格式，我终于完成了。写学年论文的经历使我这次写毕业论文变得成熟多了，我先联系导师获得了论文题目，老师问我能否做一个关于图的论文时，我说可以，其实，图对我来说，是一块很让自己头疼的内容，但喜欢挑战的我还是雄心勃勃的决定做一个关于图的毕业设计。我先从网上查询关于

14、图的应用，如邮递员问题、城市扫雪问题、乘坐公交车问题等，于是，我就将目标锁定在关于图的最短路径问题上，最短路径的问题老师讲过，而且，与我们的生活息息相关。由于时间有限，我决定做一个与图有关的小应用程序，是关于我非常熟悉的校园中各个教学楼间的路径的探索。终于搞清楚了图的基本术语、图的存储、最短路径的算法。我先开始写代码，虽然代码不多，但仍然困难重重，代码编写逻辑虽合理，却运行不出正确的结果。代码编写通过后，我舒了一口气，接下来将最短路径融入实际生活中，平时东南西北不分的的自己开始硬头皮勾画校园教学楼网络分布图，并根据自16己平时的经验给每条路上加了相应的权值。接下来是小应用程序界面的设计，为了在

15、图形界面中正确显示出最终结果，让我花了很多时间和心思。我的毕业设计也完成了，同时非常感谢指导老师珍贵的意见，由于时间有限，有很多地方还需要完善，如 Floyd 算法的优化设计，应用程序小界面更加的有好美观等。还需要自己更多的努力。17说 明：1. 成绩评定均 采用五级分制，即优、良、中、及格、不及格。2. 评语内容包括：学术价值、实际意义、达到水平、学术观点及论证有无错误等。指导教师职称预评成绩指 导 教 师 预 评 评 语年 月 日答辩小组评定成绩答辩委员会终评成绩答 辩 小 组 评 审 意 见答辩小组组长（签字）：年 月 日答 辩 委 员 会 终 评 意 见答辩委员会主任（签章）：年 月 日