毕业论文——用Floyd算法计算校园教学楼间的路径

毕 业 论 文题 目： 用Floyd算法实现对校园教学楼间的路径的计算 学 院： 计算机科学与工程学院 专 业： 计算机科学与技术 毕业年限： 学生姓名： 学 号： 指导教师： 用Floyd算法计算校园教学楼间的路径摘要：最短路径是图论中的一个重要问题，具有很高的实用价值，在地图中寻找最佳路径就是其重要的价值之一。本文章通过个人的经验，草拟了一份师大个教学楼间的带权图，用邻接矩阵存储，并通过求解网络中任意两点之间最短路径的高效方法Floyd算法来实现查找从一个教学楼到另一个教学楼的最短有效路径，为了便于实际操作，并用java中的swing组件实现简单的图形界面。关键字：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.3Floyd算法83.1.4两种算法的比较94编程实现104.1编程语言的介绍104.2程序实现的流程图104.3程序源代码114.3.1 图形界面的的源代码。114.3.2 最短路径算法的代码。124.3.3运行程序14参考文献155结束语161西北师大教学楼的简单分布图下面是我画的师大一些重要的教学楼的分布图，如图1-1图1-1.西北师大教学楼的简单分布图 2 图的简介2.1图的基本概念图（Graph）由两个集合V(vertex)和E（edge）组成,记为G = (V , E),其中，V是定顶点的集合，记为V(G)，E是两个不同顶点（顶点对）边的有限集合，记为E(G)。2.2图的存储结构图的存储除了要存储个顶点本身的信息外，还要存储定点与定点之间所有的关系（边的关系），图的存储结构一般有四种，分别是邻接矩阵、邻接表、十字邻接表存储、邻接多重表存储。由于用邻接矩阵存储有利于最短路径算法的实现，而且图中的定点数目有限，故本文章用邻接矩阵存储图中的信息。2.2.1 邻接矩阵的数据类型邻接矩阵的数据类型定义如下：define MAXV 99/最大顶点个数Class VertexType int no;/顶点编号 InfoType info;/顶点其他信息;public class MGraph int edgesMAXVMAXV;/邻接矩阵 int n,e;/顶点数，弧数 VertexType vexsMAXV;/存放顶点信息 ；2.2.2 邻接矩阵存储方法邻接矩阵是表示顶点之间相邻关系的矩阵。设G= （V , E）是具有n（n 0）个顶点的图，顶点的顺序依次为（v0,v1,.,vn-1）,则G的邻接矩阵A是n阶方阵，其定义如下：（1）如果G是无向图，则：Aij = （2） 如果G是有向图，则： Aij = （3）如果G是带权无向图，则： Aij = （4）如果G是带权有向图，则：Aij = 2.2.3 邻接矩阵的特点邻接矩阵的特点如下：l 邻接矩阵的表示是唯一的。l 无向图的邻接矩阵是一个对称矩阵，可以用压缩存储的方法存储。l 用邻接矩阵的方法存储图，要确定图中有多少边，则按行、按列对每个元素进行检测，所花费的时间代价很大, 但是很容易确定图中任意两点之间是否有边相连。3 最短路径算法的介绍3.1最短路径3.1.1 最短路径的算法在一个带权的图中，若从一个顶点到另一个顶点存在路径，则通常把一条路径上的权值之和定义为该路径上的长度或称为带权路径长度。从原点到终点可能不止一条路径，把带权路径长度最短的那条路径称为最短路径，其路径长度（权值之和）称为最短路径的长度或者最短距离。图的最短路径有两方面的问题：求图中一顶点到其他顶点的最短路径，可以用Dijkstra算法实现；求图中每一对定点之间的最短路径，实现方法有两种：一是分别以图中的每个顶点为源点共调用n次Dijkstra算法；另外还有一种算法：Floyd算法。3.1.2 Dijkstra算法Dijkstra算法的基本思想为：设G(V,E)是一个带权有向图，把图中的顶点集合分为两组，第一组为已求出最短路径的顶点集合（用S表示，初始时，S中只有一个初始点，以后每求得一条最短路径v, ,v，就将v加入集合中知道全部顶点加入S集合中，算法就结束了)，第二组为其余未确定最短路径的集合（用U表示），按最短路径长度的递增次序，将顶点加入S中。在向S中添加顶点式时，总保持从源点v到S中的个顶点中的最短路径长度不大于从源点到U中任何顶点最短路径的长度，例如，若向S中添加的顶点是k,对于U中的内一个顶点u，若顶点k到顶点u有边（权值为w）,且原来从顶点v到顶点u的长度（c）大于从顶点v到顶点顶点k（c）与w之和，即 c c + w，如图3-1所示，则将v=k=u的路径作为新的最短路径。实际上，从顶点v到顶点u的这条新的最短路径是只包括S中的顶点为中间点的当前最短路径的长度，随着S中的顶点增加，当S包含所有顶点时，这条新的最短路径就是最终的最短路径kvuccw图3-1 从顶点v到u的路径比较。Dijkstra算法的具体步骤描述如下：步骤(1) 初始化：S = v(v是源点)，distvi = i = (0, ,n-1)， pathi = 步骤(2) w = minw, i,kS(把顶点k加入S中)。步骤(3) c c + w 则c = c + w,pathu = k。步骤(4) 重复步骤(2)和步骤(3)，直到所有的顶点加入S中。3.1.3 Floyd算法 Floyd算法思想可用如下表达式描述：Ai,j = costi,j (假设图G= (V,E)采用邻接矩阵cost存储)Ai,j = minAi,j，Ai,k+1 Ak+1,j(-1= k = n-2)该式是一个迭代表达式，A表示已经考虑顶点0，,k等顶点后各顶点之间的最短路径，那么Ai,j表示有v到v已经考虑顶点0，,k等顶点后各顶点之间的最短路径，在此基础上在考虑顶点k+1，求出v到v考虑了顶点k+1后的最短路径，也就是最径的解。若Ai,j已求出，顶点i到顶点k+1的路径长度为Ai,k+1，顶点k+1到顶点j的路径长度为Ak+1,j,现在考虑顶点k+1，如图3-2所示，如果Ai,k+1 +Ai,k+1 Ai,jAi.kAk,j 图 3-2 若Ai,k+1 +Ai,k+1 Ai,j,修改路径Floyd算法的具体描述： Procedure Floyd(GA，A，P)； Begin For i:=1 To n Do 最短路径长度数组和最短路径数组初始化 For j:=1 To n Do Begin Ai,j:=GAi,j；Pi,j:=-1； End； For k:=1 To n Do n次运算 For i:=1 To n Do For j:=1 To n Do Begin If (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；3.1.4两种算法的比较 正如3.1.1节所述，求图中每一对定点之间的最短路径，实现方法有两种：一是分别以图中的每个顶点为源点共调用n次Dijkstra算法，这种算法的时间复杂度为O（n）；另外还有一种算法：Floyd算法，它的时间复杂度仍然为O（n），但思路简单，本文采用Floyd算法。4编程实现 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 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是一种简单的，面向对象的，分布式的，解释型的，健壮安全的，结构中立的，可移植的，性能优异、多线程的动态语言。4.2程序实现的流程图程序设计流程如图4-1所示： 开始单击按钮引发事件输出结果是否继续是否结束输入数据即选择起点与终点。单击“查找”按钮用floyd算法进行最短路径计算。输出最短路径。 图4-1 程序设计思想流程图4.3程序源代码4.3.1 图形界面的的源代码。 /布局管理器设为空 setLayout(null); /起点下拉列表设置。jComboBox1 = new JComboBox(Start); /设置jComboBox1对象的带标题边框jComboBox1.setBorder(BorderFactory.createTitledBorder(请选择起点:);/设置jComboBox1对象在JFrame中的位置。 jComboBox1.setBounds(20,0,120,50); /把控件加入JFrame中 add(jComboBox1);/终点下拉列表设置 jComboBox2 = new JComboBox(End);jComboBox2.setBorder(BorderFactory.createTitledBorder(请选择终点:);jComboBox2.setBounds(170,0,120,50);add(jComboBox2); /查找按钮设置JButton jb = new JButton(查找);jb.setBounds(220,55,60,25);jb.addActionListener(this);add(jb);/显示标签设置JLabel jl1 = new JLabel(最短路径为：);jl1.setBounds(10,90,80,30); add(jl1); /显示文本设置 textarea = new TextArea(); textarea.setBounds(30,130,250,40); /设置窗口标题 setTitle(校园小帮手); add(textarea);/设置本窗体显示的初始大小setSize(320,220); /设置本窗体初始可见 setVisible(true);4.3.2 最短路径算法的代码。/floyd算法public static ArrayList flody(Integer dist) Integer path=new Integerdist.lengthdist.length;/存储的是从i-j经过的最后一个节点 for (int i = 0; i dist.length; i+) /初始化路径path for (int j = 0; j disti.length; j+) pathij=-1; for(int k=0;kdist.length;k+)/开始最短路径的计算 for (int i = 0; i dist.length; i+) if(i = k)continue; elsefor(int j = 0; j (distik+ distkj) /修改路径 pathij=k;/存储的是从i-j经过的最后一个节点 distij=(distik + distkj); ArrayList list =new ArrayList(); list.add(dist); list.add(path); return list; 4.3.3 运行程序 鼠标单击（1） 选择起点 选择起点 鼠标单击（2） 选择终点 选择终点鼠标单击(3)查找路径查询结果参考文献1. 李春葆. 数据结构教程.第二版.北京.清华大学出版社.20072. Robert L.Kruse、Alexander J.Ryba .数据结构与程序设计.影印版.北京.高等教育出版社.20013. 陈浩 等.Java应用开发指南.珍藏版.北京.清华大学出版社4. 谭浩强.C+程序设计.北京.清华大学出版社.20065. William.J.Collins.陈曙晖.数据结构和Java集合框架.北京.清华大学出版社6. 李钟尉、陈丹丹.Java开发实战1200例第二卷.北京.清华大学出版社.20117. 郝自军 、何尚录.最短路问题的Floyd算法的若干讨论. 重庆工学院学报(自然科学). 2008.055 结束语毕业设计终于完成了，除了变得轻松和释然外，心里还有遗憾和失落，就像一个长跑运动员跑完了自己的赛程，是不是第一并不重要，关键是自己努力了，坚持下来了，自己终于跑到终点了。记得上次写学年论文时虽然很早就准备了，但由于第一次写论文设计，准备了一大堆东西，却很混乱，没条理，感谢老师的细心指导，通过多次修改完善包括代码设计和论文内容，还有论文格式，我终于完成了。写学年论文的经历使我这次写毕业论文变得成熟多了，我先联系导师获得了论文题目，老师问我能否做