交通咨询系统的最短路径算法与实现_学位论文.doc

《交通咨询系统的最短路径算法与实现_学位论文.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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五、设计总结2830致谢29参考文献29交通咨询系统的最短路径算法与实现内容摘要目前在交通咨询领域，最短路径算法的研究和应用越来越多，其中最短路径算法的效率问题是普遍关注并且在实际应用中迫切需要解决的问题。随着现代生活节奏的加快，以及城市汽车数量的不断增加，交通网络也越来越发达，在交通工具和交

3、通方式不断更新的今天，人们在旅游、出差或者其他出行时，不仅会关心费用问题，而且对里程和所需要的时间等问题也特别感兴趣。为了能够更方便人们的出行，我们就应该以最短路径问题建立一个交通咨询系统。这样的一个交通系统可以回答人们提出的有关交通的所有问题，比如任意一个城市到其他城市的最短路径，或者任意两个城市之间的最短路径问题。本文通过对几个常见的最短路径算法的分析，研究和实现，即经典的Dijkstra算法、Floyd算法。讨论了各个算法的思想、原理、实现方法、数据结构还有算法描述，并从时间以及空间的复杂度进行分析比较其优点和缺陷以及具体的实用性。针对现代交通网络现状特点

4、，分析和研究适合道路的经典最短路径算法，探讨了在交通网络路线优化过程中需要特别处理的几个问题，并在理论上给出相应的合理的解决方案。关键词：交通咨询最短路径Dijkstra算法Floyd算法30ShortestpathalgorithmoftheTransportAdvisorySystemDesignandImplementationAbstractCurrentlyinthefieldoftrafficadvisory,researchandapplicationoftheshortestpathalgorithmbecomemoreandmore,where

5、intheefficiencyoftheshortestpathalgorithmisacommonconcernandinpracticeisanurgentneedtosolvetheproblem.Withthepaceofmodernlifeaccelerate,aswellastheincreasingnumberofcitycar,transportationnetworksismoredeveloped,invehiclesandtransportationconstantlyupdatedtoday,peopleintourism,travelo

6、rothertraveltime,notonlyconcernedaboutcosts,butalsothetimerequiredmileageandotherissuesarealsoofparticularinterest.Tobemoreconvenientforpeopletotravel,weshouldbuildashortestpathproblemtrafficadvisorysystem.Suchatransportationsystemcananswerallquestionsrelatedtotransportationhavebeenp

7、roposed,suchastheshortestpathtoanyonecitytoothercities,oranyshortestpathbetweenthetwocities.ThroughtheanalysisofseveralcommonshortestpathalgorithmresearchandrealizedthattheclassicalDijkstraalgorithm,Floydalgorithm.Wediscussedvariousalgorithmsideology,theory,implementation,datastructu

8、res,aswellas