1、1毕 业 论 文题 目： 用 Floyd 算法实现对校园教学楼间的路径的计算 学 院： 计算机科学与工程学院 专 业： 计算机科学与技术 毕业年限： 学生姓名： 学 号： 指导教师： 2用 Floyd 算法计算校园教学楼间的路径摘要：最短路径是图论中的一个重要问题，具有很高的实用价值，在地图中寻找最佳路径就是其重要的价值之一。本文章通过个人的经验，草拟了一份师大个教学楼间的带权图，用邻接矩阵存储，并通过求解网络中任意两点之间最短路径的高效方法 Floyd 算法来实现查找从一个教学楼到另一个教学楼的最短有效路径，为了便于实际操作，并用 java 中的 swing 组件实现简单的图形界面。关键字：
2、Floyd 算法，邻接矩阵，最短路径,JavaSwing 组件编程，图的应用。目录1 西北师大教学楼的简单分布图 .32 图的简介 .42.1 图的基本概念 .42.2 图的存储结构 .42.2.1 邻接矩阵的数据类型 .52.2.2 邻接矩阵存储方法 .52.2.3 邻接矩阵的特点 .63 最短路径算法的介绍 .63.1 最短路径 .63.1.1 最短路径的算法 .63.1.2 Dijkstra 算法 .73.1.3 Floyd 算法 .83.1.4 两种算法的比较 .94 编程实现 .104.1 编程语言的介绍 .104.2 程序实现的流程图 .104.3 程序源代码 .114.3.1 图
3、形界面的的源代码。 .114.3.2 最短路径算法的代码。 .124.3.3 运行程序 .14参考文献 .155 结束语 .1631 西北师大教学楼的简单分布图下面是我画的师大一些重要的教学楼的分布图，如图 1-1图 1-1.西北师大教学楼的简单分布图42 图的简介2.1 图的基本概念图（Graph ）由两个集合 V(vertex)和 E（edge）组成,记为 G = (V , E),其中，V 是定顶点的集合，记为 V(G)，E 是两个不同顶点（顶点对）边的有限集合，记为 E(G)。2.2 图的存储结构图的存储除了要存储个顶点本身的信息外，还要存储定点与定点之间所有的关系（边的关系） ，图的存
4、储结构一般有四种，分别是邻接矩阵、邻接表、十字邻接表存储、邻接多重表存储。由于用邻接矩阵存储有利于最短路径算法的实现，而且图中的定点数目有限，故本文章用邻接矩阵存储图中的信息。2.2.1 邻接矩阵的数据类型邻接矩阵的数据类型定义如下：define MAXV 99/最大顶点个数Class VertexTypeint no;/顶点编号InfoType info;/顶点其他信息;public class MGraphint edgesMAXVMAXV;/邻接矩阵int n,e;/顶点数，弧数VertexType vexsMAXV;/存放顶点信息 ；2.2.2 邻接矩阵存储方法邻接矩阵是表示顶点之间相
5、邻关系的矩阵。设 G= （V , E）是具有 n（n 50）个顶点的图，顶点的顺序依次为（v0,v1,.,vn-1）,则 G 的邻接矩阵 A 是 n 阶方阵，其定义如下：（1）如果 G 是无向图，则：Aij = 其 他若0E(),(1vji（2） 如果 G 是有向图，则： Aij = 其 他若 (G),vji（3）如果 G 是带权无向图，则：Aij = 其 他， 且若vjijviij0 E(),(w（4）如果 G 是带权有向图，则：Aij = 其 他， 且若 vjijviij0 (G),2.2.3 邻接矩阵的特点邻接矩阵的特点如下： 邻接矩阵的表示是唯一的。 无向图的邻接矩阵是一个对称矩阵，可
6、以用压缩存储的方法存储。 用邻接矩阵的方法存储图，要确定图中有多少边，则按行、按列对每个元素进行检测，所花费的时间代价很大, 但是很容易确定图中任意两点之间是否有边相连。3 最短路径算法的介绍63.1 最短路径3.1.1 最短路径的算法在一个带权的图中，若从一个顶点到另一个顶点存在路径，则通常把一条路径上的权值之和定义为该路径上的长度或称为带权路径长度。从原点到终点可能不止一条路径，把带权路径长度最短的那条路径称为最短路径，其路径长度（权值之和）称为最短路径的长度或者最短距离。图的最短路径有两方面的问题：求图中一顶点到其他顶点的最短路径，可以用 Dijkstra 算法实现；求图中每一对定点之间
7、的最短路径，实现方法有两种：一是分别以图中的每个顶点为源点共调用 n 次 Dijkstra 算法；另外还有一种算法：Floyd 算法。3.1.2 Dijkstra 算法Dijkstra 算法的基本思想为：设 G(V,E)是一个带权有向图，把图中的顶点集合分为两组，第一组为已求出最短路径的顶点集合（用 S 表示，初始时，S中只有一个初始点，以后每求得一条最短路径 v, ,v ，就将 v 加入集合中知kk道全部顶点加入 S 集合中，算法就结束了 )，第二组为其余未确定最短路径的集合（用 U 表示） ，按最短路径长度的递增次序，将顶点加入 S 中。在向 S 中添加顶点式时，总保持从源点 v 到 S
8、中的个顶点中的最短路径长度不大于从源点到 U 中任何顶点最短路径的长度，例如，若向 S 中添加的顶点是 k,对于 U 中的内一个顶点 u， 若顶点 k 到顶点 u 有边（权值为 w ）,且原来ku从顶点 v 到顶点 u 的长度（c ）大于从顶点 v 到顶点顶点 k（c ）与 w 之和，v v即 c c + w ，如图 3-1 所示，则将 v=k=u 的路径作为新的最短路径。uk实际上，从顶点 v 到顶点 u 的这条新的最短路径是只包括 S 中的顶点为中间点的当前最短路径的长度，随着 S 中的顶点增加，当 S 包含所有顶点时，这条新的最短路径就是最终的最短路径7图 3-1 从顶点 v 到 u 的
9、路径比较。Dijkstra 算法的具体步骤描述如下：步骤(1) 初始化：S = v(v 是源点)，distvi = i = (0, ,n-1)，其 他， 且若vjijviij0E(G),wpathi = 其 他有 边 时到当1)i(步骤(2) w = minw , i ,kS(把顶点 k 加入 S 中)。vkvU步骤(3) c c + w 则 c = c + w ,pathu = k。uukuvuku步骤(4) 重复步骤 (2)和步骤 (3)，直到所有的顶点加入 S 中。3.1.3 Floyd 算法Floyd 算法思想可用如下表达式描述：A i,j = costi,j (假设图 G= (V,E
10、)采用邻接矩阵 cost 存储)1A i,j = minA i,j，A i,k+1 A k+1,j(-1= Ai,jk1kA i.kk A k,jk图 3-2 若 A i,k+1 +A i,k+1 A i,j,修改路径kkkFloyd 算法的具体描述 ：Procedure Floyd(GA，A， P)；BeginFor i:=1 To n Do 最短路径长度数组和最短路径数组初始化For j:=1 To n DoBeginAi,j:=GAi,j；Pi,j:=-1；End；For k:=1 To n Do n 次运算For i:=1 To n DoFor j:=1 To n DoBeginIf
11、(i=k)or(j=k)or(i=j) Then Continue；无需计算，直接进入一轮循环If Ai,k+Ak,jAi,j Then Begin 找到更短路径、保存Ai,j：= Ai,k+Ak,j； Ai,j用于保存最短路径长度Pi,j：= k； Pi,j用于保存最短路径End；End；End；93.1.4 两种算法的比较正如 3.1.1 节所述，求图中每一对定点之间的最短路径，实现方法有两种：一是分别以图中的每个顶点为源点共调用 n 次 Dijkstra 算法，这种算法的时间复杂度为 O（n ） ；另外还有一种算法：Floyd 算法，它的时间复杂度仍然为3O（n ） ，但思路简单，本文采
12、用 Floyd 算法。34 编程实现4.1 编程语言的介绍本文章的小程序是用 Java 编程语言编写的， Java 是由 Sun Microsystems公司于 1995 年 5 月推出的 Java 程序设计语言（以下简称 Java 语言）和 Java 平台的总称。用 Java 实现的 HotJava 浏览器（支持 Java applet）显示了 Java 的魅力：跨平台、动态的 Web、Internet 计算。从此， Java 被广泛接受并推动了Web 的迅速发展，常用的浏览器现在均支持 Java applet。另一方面，Java 技术也不断更新。Java 平台由 Java 虚拟机（Java
13、 Virtual Machine）和 Java 应用编程接口（Application Programming Interface、简称 API）构成。Java 应用编程接口为 Java 应用提供了一个独立于操作系统的标准接口，可分为基本部分和扩展部分。在硬件或操作系统平台上安装一个 Java 平台之后，Java 应用程序就可运行。现在 Java 平台已经嵌入了几乎所有的操作系统。这样 Java 程序可以只编译一次，就可以在各种系统中运行。Java 应用编程接口已经从 1.1x 版发展到 1.2 版。目前常用的 Java 平台基于 Java1.4，最近版本为 Java1.7。Java 分为三个体系 J2SE(Java2 Standard Edition)，J2EE(Java 2 Platform,Enterprise Edition)，J2ME(Java 2 Micro Edition)。Java 是一种简单的，面向对象的，分布式的，解释型的，健壮安全的，结构中立的，可移植的，性能优异、多线程的动态语言。104.2 程序实现的流程图程序设计流程如图 4-1 所示：开始单击按钮引发事件输出结果是否继续是否结束输入数据即选择起点与终点。单击“查找”按钮用 floyd 算法进行最短路径计算。输出最短路径。图 4-1 程序设计思想流程图
