交通咨询系统的最短路径算法与实现毕业论文(编辑修改稿)

交通咨询系统的最短路径算法与实现毕业论文(编辑修改稿)内容摘要：

O(N log N)。 （三）研究内容 本文的研究范畴是智能交通系统中的最短路径算法，研究领域是城市路网中的限制搜索区域最短路径算法，研究内容是典型城市路网中最短路径算法的理论研究及实验验证，研究目的是保证查询结果可靠的情况下，最大程度降低最短路径查询时间，研究方法是充分研究和利用城市路网的特 征参数，降低最短路径算法冗余度和复杂度，性能验证是软件仿真预测和实测数据统计双重评估标准。 （四） 论文结构 论文共分为六个章节，各章内容组织如下 : 第一章为绪论，首先叙述了本课题研究的背景意义，然后依次回顾了智能交通系统的发展历程，介绍了最短路径算法的研究现状，最终引出论文的工作内容 并给出了论文组织结构。 第二章是本文的理论研究基础，介绍城市路网中各种限制搜索区域最短路径算法，着重讨论了Dij kstra算法、 Floyd算法的运行机理。 第三章是 介绍了系统的开发工具及系统的运行环境。 第四章 分析 交通咨询系统的最短路径 算法实现代码的编写。 第五章 简要介绍了系统的界面设计。 第六章 总结，提出文章的缺点与不足之处，谈谈自己的想法，并提出发展期望。 二、 最短路径算法 相关原理 本章介绍城市路网中各种限制搜索区域最短路径算法，重点讨论 Dijkstra 算法、 Floyd 算法的实现原理。 （一） Dijkstra 算法 Dijkstra 算法是一个按权值大小递增的次序产生最优路径的算法，用于计算从有向图中任意结点到其他结点的最优路径。 设一个有向图 G=(V,E),已知各边的权值，以某指定点 为源点，求到图的其余各点的最短路径。 5 1959 年狄克斯特拉（ Dijkstra）提出一个按路径“长度”递增的次序产生最短路径的算法，即：把图中所有的顶点分成两组，第一组 S包括已经确定最短路径的顶点，初始时只含有源点；第二组 VS中包括尚未包括最短路径的顶点，初始时含有图中初源点之外的所有其他顶点。 按路径长度递增的顺序计算源点到各顶点的最短路径，逐个把第二组中的顶点加到第一组中去，直至 V=S。 有向网用邻接矩阵 cost[][]表示，其中规定：（ 1）如果两个顶点之间无直接路径，即 弧对应权 值为无穷大；（ 2）两个顶点之间有直接路径 的，矩阵中的权值就是 弧对应的公路长度；（ 3） 对应的值为 0。 S 集合初始存放最短路径的源点，计算过程中将已经确定了最短路径的顶点加到 S中去。 Dist 数组最终存放源点到各顶点的最短路径结果。 Path 数组最终存放源点到个顶点的最短路径经过的顶点。 如下图所示： 由 F到 A的路径有三条： F A： 24； F B A： 5+18=23； F B C A： 5+7+9=21 第一条最短路径为与源点 V邻接顶点的弧集合中， 权值最小的弧。 下一条长度次短的最短路径是：假设该次短路径的终点是 ，则这条路径或者是 ， 或者是 ，它的长度或者是从V到 弧上的权值，或者是 V到 路径长度与 到 的弧上权值之和。 引进一个辅助向量 D，它的每个分量 D[i]表示当前找到的从 源点 V到每 个终点 的最短路径的长度。 设用带权的邻接矩阵 dist[i][j]来表示有向图， dist[i][j]表示弧 上的权值，若不存在，则置 dist[i][j]为某一最大值。 向量 S为已找到从 V出发的最短路径的终点的集合，其初始值为空集。 算法按下面的步骤进行： 6 ① 从 V出发到图 上其余各个顶点（终点） 可能达到的最短路径长度的初始值为： D[i]=dist[ORDINAL(V)][i]， Vi∈ V 其中 ORDINAL(V)表示顶点 V在有向图中的序号 ② 选择 Vj，使 D[j]=Min{D[i]|Vi S， Vi∈ V} Vj就是当前求得的一条从 V出发的最短路径的终点，且令 S=S∪ {j} 即将 j加入到 S集合中。 ③ 修改从 V出发到集合 VS上所有顶点 Vk 可达到的最短路径长度。 如果 D[j]+dist[j][k]D[k] 则 修改 D[k]为 D[k]=D[j]+dist[j][k] ④ 重复操作 （ 2），（ 3） 共 n1 次。 最后求得从 V 到图上其余各定点的最短路径是依路径长度递增的序列。 例：对上图，邻接矩阵为 最短路径求解过程图例， F为源点； ①
初始状态 ， A B C D E F S D 求得 min{D}={24,5, ∞ ,25, ∞ }=5，最短路径 F B ② 以 D[j]修改（即 F B路径长度修改 ） 向量 D， A B C D E F S 0 0 0 0 0 1 24 5 ∞ 25 ∞ 0 FA FB 无 FD 无 无 0 1 0 0 0 1 7 D 求得 min{D}={23,12, 25, ∞ }=12，最短路径 F B C ③ 以 D[j]修改（即 F B C路径长度修改）向量 D， A B C D E F S D 求得 min{D}={21, 25, ∞ }=21，最短路径 F B C A ④ 以 D[j]修改（即 F B C A路径长度修改）向量 D， A B C D E F S D 求得 min{D}={25, ∞ }=25，最短路径 F D ⑤ 以 D[j]修改（即 F D路径长度修改）向量 D， A B C D E F S D 求得 min{D}={∞ }=∞ ， 即 F E无路径 （二） Floyd 算法 FloydWarshall算法 （ FloydWarshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。 FloydWarshall算法的时间复杂度为 O(N3)，空间复杂度为 O(N2)。 23 5 12 25 ∞ 0 FBA FB FBC FD 无 无 0 1 1 0 0 1 21 5 12 25 ∞ 0 FBCA FB FBC FD 无 无 1 1 1 0 0 1 21 5 12 25 ∞ 0 FBCA FB FBC FD 无 无 1 1 1 1 0 1 21 5 12 25 ∞ 0 FBCA FB FBC FD 无 无 8 ： 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的 最短路径的距离。 ：。 所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。 如果是更新它。 算法过程矩阵的计算 十字交叉法 方法：两条线，从左上角开始计算一直到右下角 如下所示给出矩阵，其中矩阵 A是邻接矩阵，而矩阵 Path记录 u,v两点之间最短路径所必须经过的点 相应计算方法如下： 9 10 最后 A3即为所求结果。 三、开发工具与环境 （一） Java 技术 1. Java 简介 Java是由 SunMicrosystems公司于 1995年 5月推出的 Java程序设计语言（以下简称 Java语言）和 Java平台的总称。 用 Java实现的 HotJava浏览器（支持 Javaapplet）显示了 Java的魅力：跨平台、动感的 Web、 Inter 计算。 从此， Java 被广泛接受并推动了 Web 的迅速发展，常用的浏览器现在均支持 Javaapplet。 另一方面， Java技术也不断更新。 Java 平台由 Java 虚拟机（ Java Virtual Machine）和 Java 应用编程接口（ Application ProgrammingInterface、简称 API）构成。 Java应用编程接口为 Java 应用提供了一个独立于操 作系统的标准接口，可分为基本部分和扩展部分。 在硬件或操作系统平台上安装一个 Java平台之后，Java 应用程序就可运行。 现在 Java 平台已经嵌入了几乎所有的操作系统。 这样 Java 程序可以只编译一次，就可以在各种系统中运行。 Java应用编程接口已经从。 目前常用的 Java平台基于 ，最近版本为。 Java分为三个体系 JavaSE， JavaEE， JavaME。 Java的特点是 ： (1) Java 的简单性：和 C++相比，语法简单了，取消了指针的语法；内存分配和 回收不需要我们来过渡关注， C++可以多继承，但 java只能是单继承，相对于类来说。 （注：接口可以多继承）使用 Asp可以组合 HTML页、脚本命令和 ActiveX组件以创建交互的 Web 页和基于 Web的功能强大的应用程序。 (2) java面向对象： java算是纯面向对象，但 jquery是更纯的面向对象。 在 java编程 思想这本书说过，“ Everything is object!” 这样便于人类的构思和设计，更符 合人们的思考问题方式。 (3) 分布式：主要还是用在 EJB上。 (4) 安全性： java的语法限定了源程序的安全性，首先编译器会进行源代码的第一步检查。 (5) 跨平台： java 能够跨越不同的操作系统平台，平台无关性 怎么跨平台呢。 主要是在不同的操作系统中， JVM规范都是一样的，被 JVM加载成各个操作系统所支持的，屏蔽了底层操作系统的差异。 (6) 高性能：开闭原则 对扩展开放，对修改关闭 java是即时编译的。 (7) 多线程。 11 的处理流程 (1) 首先编辑 .java源程序。 (2) 编译成 .class字节码文件 byte code（一种二进制文件）。 (3) 最后被 java虚拟机 （ JVM）加载解释并执行。 四、 交通咨询系统的实现 （一）系统分析 为了保证系统能够长期、安全、稳定、可靠、高效的运行，系统应该满足以下的性能需求： 统一处理的准确性和及时性：系统处理的准确性和及时性是系统的必要性能。 在系统设计和开发过程中，要充分考虑系统当前和将来可能承受的工作量，使系统的处 理能力和响应时间能够满足企业对员工信息处理的需求。 系统的开放性和可扩充性：系统在开发过程中，应该充分考虑以后的可扩充性。 例如数据表中用户选择字段方式的改变，用户查询的需求也会不断的更新和完善。 所有这些，都要求系统提供足够的手段进行功能的调整和扩充。 而要实现这一点，应通过系统的开放性来完成，既系统应是一个开放系统，只要符合一定的规范，可以简单的加入和减少系统的模块，配置系统的硬件。 通过软件的修补、替换完成系统的升级和更新换代。 系统的易用性和易维护性：要实现这一点，就要求系统应该尽量使用用户熟悉的术语和中文 信息的界面；针对用户可能出现的使用问题，要提供足够的在线帮助，缩短用户对系统熟悉的过程。 系统的数据要求： (1) 数据录入和处理的准确性和实时性； (2) 数据的一致性与完整性； (3) 数据的共享与独立性。 设计内容 ： 设计一个交通咨询系统，能让旅客咨询任意一个城市到另一个城市之间的最短路径问题。 该交通咨询系统设计共三部分，一是建立交通网络图的存储结构；二是解决单源路径问题；最后再实现两个城市之间的最短路径问题。 12 设计思想 用邻接矩阵来存储交通。