交通咨询系统的最短路径算法与实现毕业论文

PAGE 本科毕业论文(设计)论文题目：交通咨询系统的最短路径算法与实现PAGE31 毕业设计（论文）原创性声明和使用授权说明原创性声明本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究工作及取得的成果。尽我所知，除文中特别加以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为获得及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。作者签名：日期：指导教师签名：日期：使用授权说明本人完全了解大学关于收集、保存、使用毕业设计（论文）的规定，即：按照学校要求提交毕业设计（论文）的印刷本和电子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。作者签名：日期：

学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名： 日期：年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。涉密论文按学校规定处理。作者签名： 日期：年月日导师签名：日期：年月日

注意事项1.设计（论文）的内容包括：1）封面（按教务处制定的标准封面格式制作）2）原创性声明3）中文摘要（300字左右）、关键词4）外文摘要、关键词5）目次页（附件不统一编入）6）论文主体部分：引言（或绪论）、正文、结论7）参考文献8）致谢9）附录（对论文支持必要时）2.论文字数要求：理工类设计（论文）正文字数不少于1万字（不包括图纸、程序清单等），文科类论文正文字数不少于1.2万字。3.附件包括：任务书、开题报告、外文译文、译文原文（复印件）。4.文字、图表要求：1）文字通顺，语言流畅，书写字迹工整，打印字体及大小符合要求，无错别字，不准请他人代写2）工程设计类题目的图纸，要求部分用尺规绘制，部分用计算机绘制，所有图纸应符合国家技术标准规范。图表整洁，布局合理，文字注释必须使用工程字书写，不准用徒手画3）毕业论文须用A4单面打印，论文50页以上的双面打印4）图表应绘制于无格子的页面上5）软件工程类课题应有程序清单，并提供电子文档5.装订顺序1）设计（论文）2）附件：按照任务书、开题报告、外文译文、译文原文（复印件）次序装订

目录 序言 1一、绪论 2（一）课题的背景和意义 2（二）研究现状 21.最短路径算法研究现状 22.最短路径算法分类 33.算法时间复杂度 3（三）研究内容 4（四）论文结构 4二、最短路径算法相关原理 4（一）Dijkstra算法 41.算法思想分析 52.实现思路 53.计算步骤 5（二）Floyd算法 71.算法思想原理： 82.算法描述： 83.Floyd算法过程矩阵的计算十字交叉法 8三、开发工具与环境 10（一）Java技术 101.Java简介 102.Java的处理流程 11四、交通咨询系统的实现 11（一）系统分析 111.系统的设计内容： 112.系统的设计思想 123.系统设计流程 12（二）系统功能结构 121.系统构架设计 122.系统详细设计 143.测试数据及分析 26五、设计总结 28致谢 29参考文献 29交通咨询系统的最短路径算法与实现内容摘要目前在交通咨询领域，最短路径算法的研究和应用越来越多，其中最短路径算法的效率问题是普遍关注并且在实际应用中迫切需要解决的问题。随着现代生活节奏的加快，以及城市汽车数量的不断增加，交通网络也越来越发达，在交通工具和交通方式不断更新的今天，人们在旅游、出差或者其他出行时，不仅会关心费用问题，而且对里程和所需要的时间等问题也特别感兴趣。为了能够更方便人们的出行，我们就应该以最短路径问题建立一个交通咨询系统。这样的一个交通系统可以回答人们提出的有关交通的所有问题，比如任意一个城市到其他城市的最短路径，或者任意两个城市之间的最短路径问题。本文通过对几个常见的最短路径算法的分析，研究和实现，即经典的Dijkstra算法、Floyd算法。讨论了各个算法的思想、原理、实现方法、数据结构还有算法描述，并从时间以及空间的复杂度进行分析比较其优点和缺陷以及具体的实用性。针对现代交通网络现状特点，分析和研究适合道路的经典最短路径算法，探讨了在交通网络路线优化过程中需要特别处理的几个问题，并在理论上给出相应的合理的解决方案。关键词：交通咨询最短路径Dijkstra算法Floyd算法ShortestpathalgorithmoftheTransportAdvisorySystemDesignandImplementationAbstractCurrentlyinthefieldoftrafficadvisory,researchandapplicationoftheshortestpathalgorithmbecomemoreandmore,whereintheefficiencyoftheshortestpathalgorithmisacommonconcernandinpracticeisanurgentneedtosolvetheproblem.Withthepaceofmodernlifeaccelerate,aswellastheincreasingnumberofcitycar,transportationnetworksismoredeveloped,invehiclesandtransportationconstantlyupdatedtoday,peopleintourism,travelorothertraveltime,notonlyconcernedaboutcosts,butalsothetimerequiredmileageandotherissuesarealsoofparticularinterest.Tobemoreconvenientforpeopletotravel,weshouldbuildashortestpathproblemtrafficadvisorysystem.Suchatransportationsystemcananswerallquestionsrelatedtotransportationhavebeenproposed,suchastheshortestpathtoanyonecitytoothercities,oranyshortestpathbetweenthetwocities.ThroughtheanalysisofseveralcommonshortestpathalgorithmresearchandrealizedthattheclassicalDijkstraalgorithm,Floydalgorithm.Wediscussedvariousalgorithmsideology,theory,implementation,datastructures,aswellasalgorithmsdescribedandanalyzedtocomparetheiradvantagesandshortcomings,andthepracticalityofthecomplexityofthespecifictimeandspace.Forpresentcharacteristicsofmoderntransportationnetwork,classicalshortestpathalgorithmanalysisandresearchfortheroadtoexploreseveralissuesintransportationnetworkoptimizationprocessroutesthatrequirespecialhandling,andintheorygivethecorrespondingreasonablesolution.Keywords：trafficadvisoryshortestpathDijkstraalgorithmFloydalgorithm序言最短路径问题一直在计算机科学、交通工程学、地理信息系统、运筹学等学科中是一个研究的热点，它不仅是资源分配问题解决的基础，更是线路选择问题解决的基础，特别是在地图、车辆调度以及路由选择方面有着广泛的应用。最短路径问题最直接的应用当数在地理信息领域中，例如：GIS网络分析、城市规划、电子导航等等。在交通咨询方面，寻找交通网路中两个城市之间最短的行车路线就是最短路径问题的一个典型的例子。在网络通信领域，信息包传递的路径选择问题也与最短路径息息相关。例如OPSF开放路由选择协议，每一个OPSF路由器都维护一个描述自治系统范围内到每个目标的最短路径。在图像分割问题中，最短路径也有直接的应用：在语音识别中一个主要的问题就是识别同音词，例如，to、two、too。为解决这个问题，我们需要建立一个图，顶点代表可能的单词，扁连接相邻的单词，边上的权代表相邻的可能性大小。这样图中所表示的最短路径，就是对句子最好的解释。由于最短路径问题的广泛应用，很多学者都对此进行了深入的研究，随着研究成果的成熟化也是产生了一些经典的算法。近年来，对最短路径研究的热度依然不减，并且时间复杂度也降得越来越低。从实际意义上讲，没有哪一种算法能够适用于所有的网络形式，并且在所有的网络形式上具有很好的空间和时间复杂性。这些算法又具有各自的优缺点。按照起点终点及路径的数据和特征，最短路径问题可分为五种类型：两个节点间的最短路径、所有节点的最短路径、K则最短路径、实时最短路径和指定必经点的最短路径问题。在交通网络的路径分析中，单源最短路径问题更具有普遍意义，其算法有很多种，其中采用贪心及启发策略的Dijkstra算法是目前最完善的，这是荷兰计算机科学教授EdgerW.Dijkstra(1930-2002)在1959年发现的一个算法，它以极强的抗差性得到普及和应用。再有就是由弗洛伊德（floyd）提出的另一个算法，又称传递闭包方法，求每一对节点之间的最短路径。本文就从上述几类来分别介绍最短路径的几种常用算法，并介绍最短路径问题中的算法改进。本文的其它部分组织如下：第一章概述了交通咨询系统的最短路径算法与实现的目的和意义、选题背景和技术线路。第二章介绍所要用到的技术原理。第三章介绍最短路径问题的几种算法。第四章交通咨询系统的设计及实现。第五章为总结，提出文章的缺点与不足之处，谈谈自己的想法，并提出发展期望。一、绪论（一）课题的背景和意义现如今，我国的各大城市都有着交通拥堵、道路堵塞和交通事故的频繁发生，这些都随着城市私家车的不断增加和城市汽车交通运输的加快发展越来越困扰着我们的生活，并且汽车工业发展所引发的道路交通不能满足实际需求的种种交通问题也越来越严重，越来越突出。为了解决这些问题，除了通常所用的解决办法，譬如修建必要的道路交通网、针对交通事故多发路段、修建一系列的交通安全设施，这些设施包括道路信号机、道路标识、交通指挥中心等有助于交通安全的设施，来改善道路的交通环境，提高交通的顺畅性，在一定程度上缓解交通拥挤状况。而且在必要的时候能够把道路、车辆、城市的发展需求等，大都与交通有关的基本因素归为一体，在这些基本因素的基础上，采用信息通信技术、信息自动采集技术、电子技术、网络技术、自动控制以及其他的科学技术把它们联系起来，开发一个可供模拟操作的城市交通管理系统。只有将这些方法结合起来，才能有效地解决随着交通需求不断增长、交通系统日益庞大复杂，所带来的交通问题。随着交通网络越来越发达，人们在旅游、出差或者其他出行时，不仅会关心费用问题，而且对里程和所需要的时间等问题也特别感兴趣。为了能够更方便人们的出行，我们就应该以最短路径问题建立一个交通咨询系统。这样的一个交通系统可以回答人们提出的有关交通的所有问题，比如任意一个城市到其他城市的最短路径，或者任意两个城市之间的最短路径问题。本题目的意义在于，用java软件技术实现最短路径算法在交通咨询中的重要应用，对模拟结果进行分析讨论，为将来能够有效解决各大城市的交通问题提供可靠的依据。（二）研究现状本节阐述三方面问题，首先简要回顾最短路径算法研究现状，然后概要总结最短路径算法分类，最后简单论述最短路径算法的时间复杂度。1.最短路径算法研究现状最短路径问题一直是计算机科学、运筹学、地理信息科学等学科领域的研究热点。国内外大量专家学者对此问题进行了深入研究。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。常用的路径规划方法有:平行最短路径搜索算法，蚁群算法，基于矩阵负载平衡的启发算法,EBSP*算法和Dijkstra算法等。创门在空间复杂度、时间复杂度、易实现性及应用范围等方面各具特色但是因为Dijkstra算法可以给出最可靠的最短路径，并且容易实现，所以备受青睐和并被广泛应用。经典的Dijkstra算法的时间复杂度为，直接应用到大规模城市路网时，最短路径查询时间难以令人接受，专家学者纷纷开展Dijkstra优化算法研究，概括起来，以往研究者主要是从5个方面对最短路径算法进行性能优化：(1)基于数据存储结构的优化，以空间换取时间；(2)基于路网规模控制的优化；(3)基于搜索策略的优化；(4)优先级队列结构的优化；(5)基于双向搜索的并行计算优化。本文所研究的算法内容融合了除(4)之外的所有优化策略，首先采用堆数据结构将Dijkstra算法时间复杂度降至O(NlogN)，然后采用椭圆限制算法搜索区域，控制搜索规模，限定搜索方向，最后在本文提出的二树算法中运用了并行运算思想，极大地降低了最短路径查询时间。2.最短路径算法分类由于问题类型、网络特性的不同，最短路径算法也表现出多样性。按照最短路径问题分类，最短路径问题通常可分为2个基本类型：一是单源最短路径问题，即查找某一源点到其余各点的最短路径；另一类是查找某个节点对之间的最短路径。最短路径问题具体可细分为以下几种，单源最短路径问题，单对节点间最短路径、所有节点间最短路径、k则最短路径、实时最短路径、指定必经节点的最短路径以及前N条最短路径问题等，本文的研究范畴属于单对节点间最短路径问题。按照网络类型和表示方法分类，网络可以分为稀疏网络和非稀疏网络，常用的表示方法有邻接矩阵和邻接表。邻接矩阵方法能够在o(i)时间内查询到任意两个节点之间是否有一条边，它的空间复杂度为。现实生活中网络节点往往很多，动辄上万，而且是稀疏网络居多，比如城市路网，所以用邻接矩阵表示既不现实，又浪费空间。邻接表是另一种存储网络拓扑的数据结构，它是一种链式存储结构，对于交通网络等稀疏图，采用邻接表数据结构存储网络拓扑数据空间复杂度仅为O(M十N)，不存在存储空间的浪费。邻接表数据结构已被证明是网络表达中最有效率的数据结构，在最短路径算法中得到了广泛应用。3.算法时间复杂度Dijkstra算法最简单的实现方法是用一个链表或者数组来存储所有顶点的集合，此时算法的时间复杂度是.对于边数M远少于的稀疏图来说，为节省存储空间，可以用邻接表更有效的实现该算法;为缩短算法查询时间，可以将一个二叉堆或者斐波纳契堆用作优先队列来寻找最小的顶点。当用到二叉堆的时候，算法所需的时间为O((M+N)logN);当用斐波纳契堆时，算法时间复杂度为O(M+N1ogN)。对于城市路网，由于N/M介于1.5和2之间所以采用堆数据结构，Dijkstra算法时间复杂度为O(NlogN)。（三）研究内容本文的研究范畴是智能交通系统中的最短路径算法，研究领域是城市路网中的限制搜索区域最短路径算法，研究内容是典型城市路网中最短路径算法的理论研究及实验验证，研究目的是保证查询结果可靠的情况下，最大程度降低最短路径查询时间，研究方法是充分研究和利用城市路网的特征参数，降低最短路径算法冗余度和复杂度，性能验证是软件仿真预测和实测数据统计双重评估标准。（四）论文结构论文共分为六个章节，各章内容组织如下:第一章为绪论，首先叙述了本课题研究的背景意义，然后依次回顾了智能交通系统的发展历程，介绍了最短路径算法的研究现状，最终引出论文的工作内容并给出了论文组织结构。第二章是本文的理论研究基础，介绍城市路网中各种限制搜索区域最短路径算法，着重讨论了Dijkstra算法、Floyd算法的运行机理。第三章是介绍了系统的开发工具及系统的运行环境。第四章分析交通咨询系统的最短路径算法实现代码的编写。第五章简要介绍了系统的界面设计。第六章总结，提出文章的缺点与不足之处，谈谈自己的想法，并提出发展期望。二、最短路径算法相关原理本章介绍城市路网中各种限制搜索区域最短路径算法，重点讨论Dijkstra算法、Floyd算法的实现原理。（一）Dijkstra算法Dijkstra算法是一个按权值大小递增的次序产生最优路径的算法，用于计算从有向图中任意结点到其他结点的最优路径。设一个有向图G=(V,E),已知各边的权值，以某指定点为源点，求到图的其余各点的最短路径。1.算法思想分析1959年狄克斯特拉（Dijkstra）提出一个按路径“长度”递增的次序产生最短路径的算法，即：把图中所有的顶点分成两组，第一组S包括已经确定最短路径的顶点，初始时只含有源点；第二组V-S中包括尚未包括最短路径的顶点，初始时含有图中初源点之外的所有其他顶点。按路径长度递增的顺序计算源点到各顶点的最短路径，逐个把第二组中的顶点加到第一组中去，直至V=S。2.实现思路有向网用邻接矩阵cost[][]表示，其中规定：（1）如果两个顶点之间无直接路径，即弧对应权值为无穷大；（2）两个顶点之间有直接路径的，矩阵中的权值就是弧对应的公路长度；（3）对应的值为0。S集合初始存放最短路径的源点，计算过程中将已经确定了最短路径的顶点加到S中去。Dist数组最终存放源点到各顶点的最短路径结果。Path数组最终存放源点到个顶点的最短路径经过的顶点。3.计算步骤如下图所示：由F到A的路径有三条：FA：24；FBA：5+18=23；FBCA：5+7+9=21第一条最短路径为与源点V邻接顶点的弧集合中，权值最小的弧。下一条长度次短的最短路径是：假设该次短路径的终点是，则这条路径或者是，或者是，它的长度或者是从V到弧上的权值，或者是V到路径长度与到的弧上权值之和。引进一个辅助向量D，它的每个分量D[i]表示当前找到的从源点V到每个终点的最短路径的长度。设用带权的邻接矩阵dist[i][j]来表示有向图，dist[i][j]表示弧上的权值，若不存在，则置dist[i][j]为某一最大值。向量S为已找到从V出发的最短路径的终点的集合，其初始值为空集。算法按下面的步骤进行：①从V出发到图上其余各个顶点（终点）可能达到的最短路径长度的初始值为：D[i]=dist[ORDINAL(V)][i]，Vi∈V其中ORDINAL(V)表示顶点V在有向图中的序号②选择Vj，使D[j]=Min{D[i]|ViS，Vi∈V}Vj就是当前求得的一条从V出发的最短路径的终点，且令S=S∪{j}即将j加入到S集合中。③修改从V出发到集合V-S上所有顶点Vk可达到的最短路径长度。如果D[j]+dist[j][k]<D[k]则修改D[k]为D[k]=D[j]+dist[j][k]④重复操作（2），（3）共n-1次。最后求得从V到图上其余各定点的最短路径是依路径长度递增的序列。例：对上图，邻接矩阵为最短路径求解过程图例，F为源点；初始状态，ABCDEF100000S1000000∞25∞524D0∞25∞524无无FD无FBFA无无FD无FBFA求得min{D}={24,5,∞,25,∞}=5，最短路径FB②以D[j]修改（即FB路径长度修改）向量D，ABCDEF100010S1000100∞25125230∞2512523FBAFBFBC无无FBAFBFBC无无FD求得min{D}={23,12,25,∞}=12，最短路径FBC③以D[j]修改（即FBC路径长度修改）向量D，ABCDEF100110S1001100∞25125210∞2512521FBCAFBFBC无无FBCAFBFBC无无FD求得min{D}={21,25,∞}=21，最短路径FBCA④以D[j]修改（即FBCA路径长度修改）向量D，ABCDEF100111S1001110∞2512521D0∞2512521FBCAFBFBC无无FDFBCAFBFBC无无FD求得min{D}={25,∞}=25，最短路径FD⑤以D[j]修改（即FD路径长度修改）向量D，ABCDEF101111S1011110∞2512521D0∞2512521FBCAFBFBC无无FDFBCAFBFBC无无FD求得min{D}={∞}=∞，即FE无路径（二）Floyd算法Floyd-Warshall算法（Floyd-Warshallalgorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。Floyd-Warshall算法的时间复杂度为O(N3)，空间复杂度为O(N2)。1.算法思想原理：Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话，首先我们的目标是寻找从点i到点j的最短路径。从动态规划的角度看问题，我们需要为这个目标重新做一个诠释（这个诠释正是动态规划最富创造力的精华所在）从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点k到j。所以，我们假设Dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查Dis(i,k)+Dis(k,j)<Dis(i,j)是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设置Dis(i,j)=Dis(i,k)+Dis(k,j)，这样一来，当我们遍历完所有节点k，Dis(i,j)中记录的便是i到j的最短路径的距离。2.算法描述：a.从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。b.对于每一对顶点u和v，看看是否存在一个顶点w使得从u到w再到v比己知的路径更短。如果是更新它。3.Floyd算法过程矩阵的计算十字交叉法方法：两条线，从左上角开始计算一直到右下角如下所示给出矩阵，其中矩阵A是邻接矩阵，而矩阵Path记录u,v两点之间最短路径所必须经过的点相应计算方法如下：最后A3即为所求结果。三、开发工具与环境（一）Java技术1.Java简介Java是由SunMicrosystems公司于1995年5月推出的Java程序设计语言（以下简称Java语言）和Java平台的总称。用Java实现的HotJava浏览器（支持Javaapplet）显示了Java的魅力：跨平台、动感的Web、Internet计算。从此，Java被广泛接受并推动了Web的迅速发展，常用的浏览器现在均支持Javaapplet。另一方面，Java技术也不断更新。

Java平台由Java虚拟机（JavaVirtualMachine）和Java应用编程接口（ApplicationProgrammingInterface、简称API）构成。Java应用编程接口为Java应用提供了一个独立于操作系统的标准接口，可分为基本部分和扩展部分。在硬件或操作系统平台上安装一个Java平台之后，Java应用程序就可运行。现在Java平台已经嵌入了几乎所有的操作系统。这样Java程序可以只编译一次，就可以在各种系统中运行。Java应用编程接口已经从1.1x版发展到1.2版。目前常用的Java平台基于Java1.4，最近版本为Java1.6。

Java分为三个体系JavaSE，JavaEE，JavaME。Java的特点是：(1)Java的简单性：和C++相比，语法简单了，取消了指针的语法；内存分配和回收不需要我们来过渡关注，C++可以多继承，但java只能是单继承，相对于类来说。（注：接口可以多继承）使用Asp可以组合HTML页、脚本命令和ActiveX组件以创建交互的Web页和基于Web的功能强大的应用程序。(2)java面向对象：java算是纯面向对象，但jquery是更纯的面向对象。在java编程思想这本书说过，“Everythingisobject!”这样便于人类的构思和设计，更符合人们的思考问题方式。(3)分布式：主要还是用在EJB上。(4)安全性：java的语法限定了源程序的安全性，首先编译器会进行源代码的第一步检查。(5)跨平台：java能够跨越不同的操作系统平台，平台无关性怎么跨平台呢？主要是在不同的操作系统中，JVM规范都是一样的，被JVM加载成各个操作系统所支持的，屏蔽了底层操作系统的差异。(6)高性能：开闭原则对扩展开放，对修改关闭java是即时编译的。(7)多线程。2.Java的处理流程(1)首先编辑.java源程序。(2)编译成.class字节码文件bytecode（一种二进制文件）。(3)最后被java虚拟机（JVM）加载解释并执行。四、交通咨询系统的实现（一）系统分析为了保证系统能够长期、安全、稳定、可靠、高效的运行，系统应该满足以下的性能需求：统一处理的准确性和及时性：系统处理的准确性和及时性是系统的必要性能。在系统设计和开发过程中，要充分考虑系统当前和将来可能承受的工作量，使系统的处理能力和响应时间能够满足企业对员工信息处理的需求。系统的开放性和可扩充性：系统在开发过程中，应该充分考虑以后的可扩充性。例如数据表中用户选择字段方式的改变，用户查询的需求也会不断的更新和完善。所有这些，都要求系统提供足够的手段进行功能的调整和扩充。而要实现这一点，应通过系统的开放性来完成，既系统应是一个开放系统，只要符合一定的规范，可以简单的加入和减少系统的模块，配置系统的硬件。通过软件的修补、替换完成系统的升级和更新换代。系统的易用性和易维护性：要实现这一点，就要求系统应该尽量使用用户熟悉的术语和中文信息的界面；针对用户可能出现的使用问题，要提供足够的在线帮助，缩短用户对系统熟悉的过程。系统的数据要求：(1)数据录入和处理的准确性和实时性；(2)数据的一致性与完整性；(3)数据的共享与独立性。1.系统的设计内容： 设计一个交通咨询系统，能让旅客咨询任意一个城市到另一个城市之间的最短路径问题。 该交通咨询系统设计共三部分，一是建立交通网络图的存储结构；二是解决单源路径问题；最后再实现两个城市之间的最短路径问题。2.系统的设计思想用邻接矩阵来存储交通网络图的信息，运用迪杰斯特拉算法实现图上单源最短路径问题，然后运用费洛伊德算法实现图中任意一对顶点间最短路径问题，这样就会实现旅客所要咨询的问题。3.系统设计流程该交通咨询系统要完成城市网络图的存储，并要实现求任意一个城市顶点到其他城市顶点的最短路径问题，还要实现任意两个城市顶点间的最短路径问题。故设计要分成三部分，一是建立网络交通的存储结构，二是解决单源最短路径问题；最后时限两个城市之间的最短路径问题。（二）系统功能结构1.系统构架设计 首先总体的步骤是： 迪克斯特拉算法的具体流程图如下：弗洛伊德算法的具体流程图如下：2.系统详细设计程序源代码如下：//Floyd算法publicclassShortPathALG{ privateDrawing[]circleList=null;//用于存放结点 privateDrawing[]lineList=null;//用于存放线段 privateintmGraph[][]=null;//用于存储图的邻接矩阵 privateintmGraphCopy[][]=null; privateStringdis="";//最短路径结果 privateStringdrawLineRed="";//要绘制的红线路径 privateintcircleNum=0;//结点的个数 privateintlineNum=0;//线段的个数 privateDrawJPaneldrawJPanel=null; publicShortPathALG(DrawJPaneldraw){ drawJPanel=draw; //TODO最短路径的算法初始化结点和线 circleList=drawJPanel.getCircleList();//获得结点对象数组 lineList=drawJPanel.getLineList();//获得线段对象数组 circleNum=drawJPanel.getCircleCount();//获得结点的个数 lineNum=drawJPanel.getLineCount(); mGraph=newint[circleNum][circleNum];//为邻接矩阵分配空间0行、0列不用 for(inti=0;i<circleNum;i++){//初始化邻接矩阵全赋值为-1（距离不可能是负数） for(intj=0;j<circleNum;j++){ if(i==j) mGraph[i][j]=0; else{ mGraph[i][j]=32767; } } } changeLineColor();//初始化线条的颜色 mGraphInitialize();//初始化邻接矩阵 path_FLOYD(getmGraphCopy()); } //初始化线条的颜色 privatevoidchangeLineColor(){ for(inti=1;i<lineNum;i++){ lineList[i].setColor(Color.blue); } drawJPanel.repaint(); } //初始化邻接矩阵 publicvoidmGraphInitialize(){ for(inti=1;i<lineNum;i++){//循环遍历线条的起点与终点 intm=32767; try{ m=Integer.parseInt(lineList[i].name);//如果输入的距离不能转换成整形默认距离是1 }catch(Exceptione){ m=1; } //构建无向图 if(lineList[i].name.equals("")) m=1; mGraph[lineList[i].xLocation][lineList[i].yLocation]=m; mGraph[lineList[i].yLocation][lineList[i].xLocation]=m; } } //输出邻接矩阵 publicvoidshowMGraph(){ Strings="最短路径的邻接矩阵是(无向图)：\n"; for(inti=1;i<circleNum;i++){ if(!circleList[i].name.equals("")){ s=s+circleList[i].name+""; }else{ s=s+i+""; } } s=s+"\n"; for(inti=1;i<circleNum;i++){ for(intj=1;j<circleNum;j++){ s=s+mGraph[i][j]+""; } s=s+"\n"; } s=dis; lineColor();//修改路径的颜色 JOptionPane.showMessageDialog(drawJPanel,s,"最短路径", JOptionPane.PLAIN_MESSAGE); } //修改路径的颜色 privatevoidlineColor(){//修改路径的颜色 intgv[];//存放线段顶点 inti=1; StringTokenizertokenizer=newStringTokenizer(drawLineRed,"-->"); gv=newint[tokenizer.countTokens()+1];//动态的决定数组的长度 while(tokenizer.hasMoreTokens()){ Stringd=tokenizer.nextToken(); gv[i]=Integer.valueOf(d);//将字符串转换为整型 i++; } for(intj=1;j<gv.length-1;j++){ for(i=1;i<lineNum;i++){ booleanx=lineList[i].xLocation==gv[j] &&lineList[i].yLocation==gv[j+1]; booleany=lineList[i].yLocation==gv[j] &&lineList[i].xLocation==gv[j+1]; if(x||y){ lineList[i].setColor(Color.red); } } } drawJPanel.repaint(); } //最短路径算法FLOYD算法 intD[][]=null;//D存放每对顶点之间的最短路径值 intpath[][]=null;//p存放每对顶点之间的最短路径 intlength=0; publicvoidpath_FLOYD(intdata[][]){ inti,j,k; length=data.length; D=newint[length][length];//D存放每对顶点之间的最短路径值 path=newint[length][length];//p存放每对顶点之间的最短路径 for(i=1;i<length;i++){//各节点之间的初始已知路径及距离 for(j=1;j<length;j++){ D[i][j]=data[i][j];// path[i][j]=-1; } }//for for(k=1;k<length;k++){ for(i=1;i<length;i++){ for(j=1;j<length;j++){ if(i==j)//对角线上的元素（即顶点自身之间）不予考虑 continue; if(D[i][k]+D[k][j]<D[i][j]){//从i经k到j的一条路径更短 D[i][j]=D[i][k]+D[k][j]; path[i][j]=k; } } } } } publicvoidpath_DIJKSTRA(intdata[][]){ inti,j,k; length=data.length; D=newint[length][length];//D存放每对顶点之间的最短路径值 path=newint[length][length];//p存放每对顶点之间的最短路径 for(i=1;i<length;i++){//各节点之间的初始已知路径及距离 for(inty=2;y<=data.length;y++){ if(table[1][y]>0)//如果y相邻于1 L.set(y,length(1,y)); else L.set(y,Integer.MAX_VALUE); } for(intj=1;j<=V.size()-1;j++){ inty=findTheMinInL(); X.add(y); Y.remove(y); for(intjj=1;jj<table.length;jj++){ if(table[y][jj]>0) if(Y.contains(jj) &&((L.get(y)+length(y,jj))<L.get(jj))) L.set(jj,L.get(y)+length(y,jj)); } } inti,j,k; length=data.length; D=newint[length][length];//D存放每对顶点之间的最短路径值 path=newint[length][length];//p存放每对顶点之间的最短路径 for(i=1;i<length;i++){//各节点之间的初始已知路径及距离 for(j=1;j<length;j++){ D[i][j]=data[i][j];// path[i][j]=-1; } }//for for(k=1;k<length;k++){ for(i=1;i<length;i++){ for(j=1;j<length;j++){ if(i==j)//对角线上的元素（即顶点自身之间）不予考虑 continue; if(D[i][k]+D[k][j]<D[i][j]){//从i经k到j的一条路径更短 D[i][j]=D[i][k]+D[k][j]; path[i][j]=k; } } } } } //最短路径输出 publicStringdisPath(inti,intj){ //TODOAuto-generatedmethodstub booleanc1Name=!circleList[i].name.equals(""); booleanc2Name=!circleList[j].name.equals(""); if(D[i][j]==32767){ if(i!=j){ if(c1Name){ dis="从"+circleList[i].name+"到"; }else{ dis="从"+i+"到"; } if(c2Name){ dis+=circleList[j].name+"没有路径\n"; }else{ dis+=j+"没有路径\n"; } } }else{ if(c1Name){ dis="从"+circleList[i].name+"到"; }else dis="从"+i+"到"; if(c2Name){ dis+=circleList[j].name+"路径为:"; }else dis+=j+"路径为:"; if(c1Name){ dis+=circleList[i].name+"-->"; }else dis+=i+"-->"; if(c2Name){ dis+=ppath(i,j)+circleList[j].name+"\n路径长度为:" +D[i][j] +"\n"; }else{ dis+=ppath(i,j)+j+"\n路径长度为:"+D[i][j]+"\n"; } drawLineRed=i+"-->"+lineString+j; } returndis; } Strings="";//存放路径 StringlineString="";//划红线的路径 privateStringppath(inti,intj){ intk; k=path[i][j]; if(k==-1) returns; ppath(i,k); if(!circleList[k].name.equals("")){ s=s+circleList[k].name+"-->"; }else{ s=s+k+"-->"; } lineString+=k+"-->"; ppath(k,j); returns; } //得到邻接矩阵对象的副本 publicint[][]getmGraphCopy(){ mGraphCopy=newint[mGraph.length][mGraph.length]; for(inti=0;i<mGraph.length;i++) for(intj=0;j<mGraph.length;j++) mGraphCopy[i][j]=mGraph[i][j]; returnmGraphCopy; }}//Dijkstra算法packageTest;importjava.util.TreeMap;importjava.util.ArrayList;importjava.io.BufferedReader;importjava.io.InputStreamReader;importjava.io.IOException;classPoint{ privateintid;//点的id privatebooleanflag=false;//标志是否被遍历 intsum;//记录总的点个数 privateTreeMap<Integer,Integer>thisPointMap=newTreeMap<Integer,Integer>();//该点到各点的距离。 BufferedReaderbufr=newBufferedReader(newInputStreamReader(System.in)); Point(intsum){//构造函数带有顶点个数 this.sum=sum; } publicvoidsetId(intid){//设置顶点id this.id=id; } publicintgetId(){//获得顶点id returnthis.id; } publicvoidchangeFlag(){//修改访问状态。 this.flag=true; } publicbooleanisVisit(){//查看访问状态 returnflag; } publicvoidsetLenToOther()throwsIOException{//初始化改点到各顶点的距离。 System.out.println("=======请输入顶点"+(this.id+1)+"至其他各顶点的边距======="); for(inti=0;i<sum;i++){ if(i==this.id) thisPointMap.put(this.id,0); else{ System.out.print("至顶点"+(i+1)+"的距离："); booleanflag=true; intlen=0; while(flag){ try{ len=Integer.valueOf(bufr.readLine()); flag=false; }catch(NumberFormatExceptione){ System.out.print("输入有误，请重新输入："); } }; thisPointMap.put(i,len); } } } //该点到顶尖id的距离。 publicintlenToPointId(intid){ returnthisPointMap.get(id); }}classDijkstra{ publicstaticvoidmain(String[]args)throwsIOException{ ArrayList<Point>point_arr=newArrayList<Point>();//存储点集合 BufferedReaderbufr=newBufferedReader(newInputStreamReader(System.in)); System.out.print("请输入顶点个数："); intsum=0; booleanflag=true; while(flag){ try{ sum=Integer.valueOf(bufr.readLine()); flag=false; }catch(NumberFormatExceptione){ System.out.print("输入有误，请重新输入："); } }; for(inti=0;i<sum;i++){//初始化 Pointp=newPoint(sum); p.setId(i); p.setLenToOther(); point_arr.add(p); } System.out.print("请输入起始顶点id："); booleanflag2=true; intstart=0; while(flag2){ try{ start=Integer.valueOf(bufr.readLine())-1; if(start>sum-1||start<0) thrownewNumberFormatException(); flag2=false; }catch(NumberFormatExceptione){ System.out.print("输入有误，请重新输入："); } }; showDijkstra(point_arr,start);//单源最短路径遍历 } publicstaticvoidshowDijkstra(ArrayList<Point>arr,inti){ System.out.print("顶点"+(i+1)); arr.get(i).changeFlag(); Pointp1=getTopointMin(arr,arr.get(i)); if(p1==null) return; intid=p1.getId(); showDijkstra(arr,id); } publicstaticPointgetTopointMin(ArrayList<Point>arr,Pointp){ Pointtemp=null; intminLen=Integer.MAX_VALUE; for(inti=0;i<arr.size();i++){ //当已访问或者是自身或者无该路径时跳过。 if(arr.get(i).isVisit()||arr.get(i).getId()==p.getId()||p.lenToPointId(i)<0) continue; else{ if(p.lenToPointId(i)<minLen){ minLen=p.lenToPointId(i); temp=arr.get(i); } } } if(temp==null) returntemp; else System.out.print("@--"+minLen+"-->"); returntemp; }}3.测试数据及分析 Floyd算法输出结果分析如下： Dijkstra算法运行结果如下：五、设计总结 城市现代化的目的，说到底是为了人的现代化。交通咨询现代化作为城市现代化的重要内容，首先应是城市居民的生活交通现代化，这是以人为本原则的基本含义和根本要求。一般来说，实现居民生活交通现代化（主要是交通咨询的现代化）便可以满足城市生产和经营交通现代化的要求。交通咨询系统服务于城市现代化发展战略，以建设现代化交通为目标，坚持以人为本原则，优化交通结构，大力发展公共交通。 本次设计只是实现了两点之间最短路径可行距离的查询，而在现实生活中我们不仅要考虑两点之间的最短距离，还要考虑转车次数，这正是本次设计的不足之处。调查表明人们在出行时往往更倾向于转车次数较少的路线，这样便降低了人们的办事效率。因此，完善的交通咨询系统对两点之间的最短路径的查询应以转车次数少为条件。 现实世界的交通网络是复杂的，仅仅考虑道路网的时间损耗和长度分析很难满足实际需要，尤其是在城市交通网络中，在不久的将来，本系统还将致力于通过分析城市道路状况，交通管理设施，交通结构及管理状况，考虑道路的进行和单行问题，排除阻碍交通的不通路，给出两点之间的最优路径。致谢时间过得很快，一转眼四年的大学时间已近结尾，在这四年的生活学习中，许多老师和同学给予了我很多帮助。在这几个月的毕业设计中，老师和同学们给予了我很大的帮助，因此我非常感谢他们，感谢他们这么长时间的陪伴与帮助。在这里我最想感谢的人就是指导老师。在毕业设计期间，指导老师的悉心教导深刻地印在我心里，她平易近人，知识渊博，又对我们严格要求和严厉督促，这时的我在即将离开大学之际又多了一份很美好的回忆，也增加了自身的知识宽度。当然还要感学院各位老师对我的培养和关心，是他们为我创造了良好的学习环境。感谢我的同学和朋友对我在生活和学习上的无私帮助，感谢他们给我带来每一天的欢笑。感谢每位同学在论文写作期间的大力支持与鼓励。我将最诚挚的感谢献给我的父母，我今天的成绩也凝聚了他们辛勤的汗水。正是因为父母对我的关心、教诲和鼓励使我能够好好地完成学业，并向更高的目标奋斗。参考文献[1]严蔚敏。数据结构（C语言版）[M].北京，清华大学出版社，1997.[2]王海英，黄强，李传涛。图论算法及其MATLAB实现[M].北京，北京航空航天大学出版社，2010.[3]周先曙。最短路径问题及其解法研究[J],电脑知识与技术，2010，（06）.[4]王朝瑞。图论[M].北京，北京理工大学出版社，1997.[5]陆锋。最短路径算法：分类体系与研究进展[J].测绘学报，2001，（3）：269-275[6]陈箫枫，蔡秀云，唐德强。最短路径算法分析及其在公交查询的应用[J].工程图学学报，2001，（3）[7]宋晓宇，于澜洋，孙焕良，许景科。交通网络中出现阻塞路径情况下增量路径查找算法[J].沈阳建筑大学学报（自然科学版），2009，（4）[8]张池军，杨永健，赵洪波。基于路径依赖的最短路径算法的改进与实现[J].计算机工程与应用，2006，(25)[9]贺喜玲，季焕淑。最短路径算法[J].大科技（科技天地），2011，(6)[10]李擎，谢四江，童新海，王志良。一种用于车辆最短路径规划的自适应遗传算法及其与Dijkstra和A^＊算法的比较[J].北京科技大学学报,2006,(11):1082-1086基于C8051F单片机直流电动机反馈控制系统的设计与研究基于单片机的嵌入式Web服务器的研究MOTOROLA单片机MC68HC（8）05PV8/A内嵌EEPROM的工艺和制程方法及对良率的影响研究基于模糊控制的电阻钎焊单片机温度控制系统的研制基于MCS-51系列单片机的通用控制模块的研究基于单片机实现的供暖系统最佳启停自校正（STR）调节器单片机控制的二级倒立摆系统的研究基于增强型51系列单片机的TCP/IP协议栈的实现基于单片机的蓄电池自动监测系统基于32位嵌入式单片机系统的图像采集与处理技术的研究基于单片机的作物营养诊断专家系统的研究基于单片机的交流伺服电机运动控制系统研究与开发基于单片机的泵管内壁硬度测试仪的研制基于单片机的自动找平控制系统研究基于C8051F040单片机的嵌入式系统开发基于单片机的液压动力系统状态监测仪开发模糊Smith智能控制方法的研究及其单片机实现一种基于单片机的轴快流CO〈,2〉激光器的手持控制面板的研制基于双单片机冲床数控系统的研究基于CYGNAL单片机的在线间歇式浊度仪的研制基于单片机的喷油泵试验台控制器的研制HYPERL