《交通咨询系统的最短路径算法与实现毕业论文》由会员分享，可在线阅读，更多相关《交通咨询系统的最短路径算法与实现毕业论文（34页珍藏版）》请在金锄头文库上搜索。
1、本科毕业论文(设计)论文题目： 交通咨询系统的最短路径算法与实现 学生姓名： 贺 景 学 号： 0205110138 专 业： 信息管理与信息系统 班 级： 信管0201 指导教师： 陈 树 广 完成日期： 2015年 5月 5日目录序 言1一、绪 论2（一）课题的背景和意义2（二）研究现状21.最短路径算法研究现状22.最短路径算法分类33.算法时间复杂度3（三）研究内容4（四）论文结构4二、最短路径算法相关原理4（一）Dijkstra算法41.算法思想分析52.实现思路53.计算步骤5（二）Floyd算法71.算法思想原理：82.算法描述：83.Floyd算法过程矩阵的计算-十字交叉法8三
2、、开发工具与环境10（一）Java技术101. Java简介102.Java的处理流程11四、交通咨询系统的实现11（一）系统分析111.系统的设计内容：112.系统的设计思想123.系统设计流程12（二）系统功能结构121. 系统构架设计122.系统详细设计143. 测试数据及分析26五、设计总结28致谢29参 考 文 献29交通咨询系统的最短路径算法与实现内 容 摘 要目前在交通咨询领域，最短路径算法的研究和应用越来越多，其中最短路径算法的效率问题是普遍关注并且在实际应用中迫切需要解决的问题。随着现代生活节奏的加快，以及城市汽车数量的不断增加，交通网络也越来越发达，在交通工具和交通方式不断
3、更新的今天，人们在旅游、出差或者其他出行时，不仅会关心费用问题，而且对里程和所需要的时间等问题也特别感兴趣。为了能够更方便人们的出行，我们就应该以最短路径问题建立一个交通咨询系统。这样的一个交通系统可以回答人们提出的有关交通的所有问题，比如任意一个城市到其他城市的最短路径，或者任意两个城市之间的最短路径问题。本文通过对几个常见的最短路径算法的分析，研究和实现，即经典的Dijkstra算法、Floyd算法。讨论了各个算法的思想、原理、实现方法、数据结构还有算法描述，并从时间以及空间的复杂度进行分析比较其优点和缺陷以及具体的实用性。针对现代交通网络现状特点，分析和研究适合道路的经典最短路径算法，探
4、讨了在交通网络路线优化过程中需要特别处理的几个问题，并在理论上给出相应的合理的解决方案。关键词：交通咨询 最短路径 Dijkstra算法 Floyd算法Shortest path algorithm of the Transport Advisory System Design and ImplementationAbstractCurrently in the field of traffic advisory, research and application of the shortest path algorithm become more and more, where in the
5、 efficiency of the shortest path algorithm is a common concern and in practice is an urgent need to solve the problem.With the pace of modern life accelerate, as well as the increasing number of city car, transportation networks is more developed, in vehicles and transportation constantly updated to
6、day, people in tourism, travel or other travel time, not only concerned about costs, but also the time required mileage and other issues are also of particular interest. To be more convenient for people to travel, we should build a shortest path problem traffic advisory system. Such a transportation
7、 system can answer all questions related to transportation have been proposed, such as the shortest path to any one city to other cities, or any shortest path between the two cities.Through the analysis of several common shortest path algorithm research and realized that the classical Dijkstra algor
8、ithm, Floyd algorithm. We discussed various algorithms ideology, theory, implementation, data structures, as well as algorithms described and analyzed to compare their advantages and shortcomings, and the practicality of the complexity of the specific time and space. For present characteristics of m
9、odern transportation network, classical shortest path algorithm analysis and research for the road to explore several issues in transportation network optimization process routes that require special handling, and in theory give the corresponding reasonable solution. Key words：traffic advisory short
10、est path Dijkstra algorithm Floyd algorithmIII序 言最短路径问题一直在计算机科学、交通工程学、地理信息系统、运筹学等学科中是一个研究的热点，它不仅是资源分配问题解决的基础，更是线路选择问题解决的基础，特别是在地图、车辆调度以及路由选择方面有着广泛的应用。最短路径问题最直接的应用当数在地理信息领域中，例如：GIS网络分析、城市规划、电子导航等等。在交通咨询方面，寻找交通网路中两个城市之间最短的行车路线就是最短路径问题的一个典型的例子。在网络通信领域，信息包传递的路径选择问题也与最短路径息息相关。例如OPSF开放路由选择协议，每一个OPSF路由器都维护
11、一个描述自治系统范围内到每个目标的最短路径。在图像分割问题中，最短路径也有直接的应用：在语音识别中一个主要的问题就是识别同音词，例如，to、two、too。为解决这个问题，我们需要建立一个图，顶点代表可能的单词，扁连接相邻的单词，边上的权代表相邻的可能性大小。这样图中所表示的最短路径，就是对句子最好的解释。由于最短路径问题的广泛应用，很多学者都对此进行了深入的研究，随着研究成果的成熟化也是产生了一些经典的算法。近年来，对最短路径研究的热度依然不减，并且时间复杂度也降得越来越低。从实际意义上讲，没有哪一种算法能够适用于所有的网络形式，并且在所有的网络形式上具有很好的空间和时间复杂性。这些算法又具
12、有各自的优缺点。按照起点终点及路径的数据和特征，最短路径问题可分为五种类型：两个节点间的最短路径、所有节点的最短路径、K则最短路径、实时最短路径和指定必经点的最短路径问题。在交通网络的路径分析中，单源最短路径问题更具有普遍意义，其算法有很多种，其中采用贪心及启发策略的Dijkstra算法是目前最完善的，这是荷兰计算机科学教授Edger W.Dijkstra(1930-2002)在1959年发现的一个算法，它以极强的抗差性得到普及和应用。再有就是由弗洛伊德（floyd）提出的另一个算法，又称传递闭包方法，求每一对节点之间的最短路径。本文就从上述几类来分别介绍最短路径的几种常用算法，并介绍最短路径
13、问题中的算法改进。本文的其它部分组织如下：第一章概述了交通咨询系统的最短路径算法与实现的目的和意义、选题背景和技术线路。第二章介绍所要用到的技术原理。第三章介绍最短路径问题的几种算法。第四章交通咨询系统的设计及实现。第五章为总结，提出文章的缺点与不足之处，谈谈自己的想法，并提出发展期望。一、绪 论（一）课题的背景和意义现如今，我国的各大城市都有着交通拥堵、道路堵塞和交通事故的频繁发生，这些都随着城市私家车的不断增加和城市汽车交通运输的加快发展越来越困扰着我们的生活，并且汽车工业发展所引发的道路交通不能满足实际需求的种种交通问题也越来越严重，越来越突出。为了解决这些问题，除了通常所用的解决办法，
14、譬如修建必要的道路交通网、针对交通事故多发路段、修建一系列的交通安全设施，这些设施包括道路信号机、道路标识、交通指挥中心等有助于交通安全的设施，来改善道路的交通环境，提高交通的顺畅性，在一定程度上缓解交通拥挤状况。而且在必要的时候能够把道路、车辆、城市的发展需求等，大都与交通有关的基本因素归为一体，在这些基本因素的基础上，采用信息通信技术、信息自动采集技术、电子技术、网络技术、自动控制以及其他的科学技术把它们联系起来，开发一个可供模拟操作的城市交通管理系统。只有将这些方法结合起来，才能有效地解决随着交通需求不断增长、交通系统日益庞大复杂，所带来的交通问题。随着交通网络越来越发达，人们在旅游、出
15、差或者其他出行时，不仅会关心费用问题，而且对里程和所需要的时间等问题也特别感兴趣。为了能够更方便人们的出行，我们就应该以最短路径问题建立一个交通咨询系统。这样的一个交通系统可以回答人们提出的有关交通的所有问题，比如任意一个城市到其他城市的最短路径，或者任意两个城市之间的最短路径问题。本题目的意义在于，用java软件技术实现最短路径算法在交通咨询中的重要应用，对模拟结果进行分析讨论，为将来能够有效解决各大城市的交通问题提供可靠的依据。（二）研究现状本节阐述三方面问题，首先简要回顾最短路径算法研究现状，然后概要总结最短路径算法分类，最后简单论述最短路径算法的时间复杂度。1.最短路径算法研究现状最短路径问题一直是计算机科学、运筹学、地理信息科学等学科领域的研究热点。国内外大量专家学者对此问题进行了深入研究。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。常用的路径规划方法有:平行最短路径搜索算法，蚁群算
