本科毕业论文(设计)

学生姓名： 贺 景 学 号： 0205110138 专 业： 信息管理与信息系统 班 级： 信管0201 指导教师： 陈 树 广

论文题目： 交通咨询系统的最短路径算法与实现

完成日期： 2015年 5月 5日

目录

序

言 ........................................................................................................... 1

一、绪 论 ..................................................................................................... 2

（一）课题的背景和意义 ................................................................................................... 2 （二）研究现状 ................................................................................................................... 2

1.最短路径算法研究现状 ................................................................................................................... 2 2.最短路径算法分类 ........................................................................................................................... 3 3.算法时间复杂度 ............................................................................................................................... 3

（三）研究内容 ................................................................................................................... 4 （四）论文结构 ................................................................................................................... 4

二、最短路径算法相关原理 ........................................................................ 4

（一）DIJKSTRA算法 ............................................................................................................. 4

1.算法思想分析 ................................................................................................................................... 5 2.实现思路 ........................................................................................................................................... 5 3.计算步骤 ........................................................................................................................................... 5

（二）FLOYD算法 ................................................................................................................. 7

1.算法思想原理： ............................................................................................................................... 8 2.算法描述： ....................................................................................................................................... 8 3.Floyd算法过程矩阵的计算----十字交叉法 ..................................................................................... 8

三、开发工具与环境 .................................................................................. 10

（一）JAVA技术 ................................................................................................................. 10

1. Java简介 ......................................................................................................................................... 10 2.Java的处理流程 .............................................................................................................................. 11

四、交通咨询系统的实现 .......................................................................... 11

（一）系统分析 ................................................................................................................. 11

1.系统的设计内容： ......................................................................................................................... 11 2.系统的设计思想 ............................................................................................................................. 12 3.系统设计流程 ................................................................................................................................. 12

（二）系统功能结构 ......................................................................................................... 12

1. 系统构架设计 ............................................................................................................................... 12 2.系统详细设计 ................................................................................................................................. 14 3. 测试数据及分析 ........................................................................................................................... 26

五、设计总结 ............................................................................................. 28

I

致谢 ............................................................................................................ 29 参 考 文 献 ............................................................................................... 29

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

内 容 摘 要

目前在交通咨询领域，最短路径算法的研究和应用越来越多，其中最短路径算法的效率问题是普遍关注并且在实际应用中迫切需要解决的问题。

随着现代生活节奏的加快，以及城市汽车数量的不断增加，交通网络也越来越发达，在交通工具和交通方式不断更新的今天，人们在旅游、出差或者其他出行时，不仅会关心费用问题，而且对里程和所需要的时间等问题也特别感兴趣。为了能够更方便人们的出行，我们就应该以最短路径问题建立一个交通咨询系统。这样的一个交通系统可以回答人们提出的有关交通的所有问题，比如任意一个城市到其他城市的最短路径，或者任意两个城市之间的最短路径问题。

本文通过对几个常见的最短路径算法的分析，研究和实现，即经典的Dijkstra算法、Floyd算法。讨论了各个算法的思想、原理、实现方法、数据结构还有算法描述，并从时间以及空间的复杂度进行分析比较其优点和缺陷以及具体的实用性。针对现代交通网络现状特点，分析和研究适合道路的经典最短路径算法，探讨了在交通网络路线优化过程中需要特别处理的几个问题，并在理论上给出相应的合理的解决方案。

关键词：交通咨询 最短路径 Dijkstra算法 Floyd算法

II