Dijkstra算法城市立体交通最短路径问题和算法研究(2)

菜单

4.4 技巧分析 24

4.5 优化优点 25

结论 27

致谢 28

参考文献 29

1 绪论

在日常生活中，我们如果需要常常往返A地区和B地区之间，我们最希望知道的可能是从A地区到B地区间的众多路径中，哪一条路径的路途最短。最短路径问题是图论研究中的一个经典算法问题,旨在寻找图（由结点和路径组成的)中两结点之间的最短路径。算法具体的形式包括：确定起点的最短路径问题：即已知起始结点，求最短路径的问题。确定终点的最短路径问题与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。确定起点终点的最短路径问题,即已知起点和终点，求两结点之间的最短路径。全局最短路径问题：求所有的最短路径。用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”[1]。论文网

1.1 研究意义

近年来，随着城市建设的飞速发展和交通系统的不断完善，城市交通最短路径问题是图论研究中的一个重要课题，它广泛应运于交通运输、物流配送、电子导航等领域。然而，这里所说的最短路径问题并不是传统上那种单纯的距离上的最短路径，还可以引申到其他的意义上的度量，例如费用、时间等。比如城市交通中旅行者选择出游最佳路径、最可靠路径、花费最少、距离最短。行驶时间最短的问题，及统筹方法中关键路线问题等，都可以转换为最短路径问题。通过路径规划找出最优路径，具有巨大的经济效益。随着国民经济的发展，城市中车辆逐渐增多，对交通的需求也在不断增加，公路交通流量也越来越大，城市交通正在面临着越来越大的压力。在这种形势之下，静态的自主导航虽然可以规划一条“最短”路径，但是无法避开道路的交通拥挤。而动态导航则不同，经过规划可以得到一条满足用户需求的合理路径。这种导航方式不仅可以有效的避开拥堵，节省成本，而且对整个网络有良性的影响[2]。文献综述

1.2 国内外最短路径算法的发展及其概况

1.3 本文研究的问题及主题

当今社会交通问题日益严重，如何在最快的时间找到最合理的路线，是解决交通问题的关键所在。论文在分析最短路径问题的基础上，对传统的最短路径算法Dijkstra算法进行了详细的介绍，并与其他算法进行了对比，比如A*算法和遗传算法，对于种种方法各有其优缺点，当地图节点个数和弧的条数比较少时，三种算法所花费的时间差不多，当节点个数和弧的条数比较多时，A*算法最快，遗传算法其次，Dijkstra算法最慢，而且这种差距将随节点和弧数量的增加而变得更加明显。对于实际地图而言，由于节点与道路的数量一般都很的大，Dijkstra算法在搜索速度方面弱势明显。但Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等。但是由于它遍历计算的节点很多，所以效率低。每种方法各有优缺点，值得深入谈论。研究城市立体交通最短路径算法和程序设计问题。在城市的交通中怎样选择最佳的路径，选择怎样的路径距离最短、花费最少，选择最可靠的路径。鉴于交通状况的随时性，如果某一时刻拥挤，下一时刻流畅的情况下，论文讨论了交通拥挤时的最短路径问题。较详细地研究了网络分析中最短路径问题，以及在最短路径基础上的交通信息查询。对于传统最短路径问题，对其分类和特点进行归纳总结，将Dijkstra算法的原理用于计算一个节点到其他所有节点的单源路径，对于它遍历计算的节点很多，效率低等缺点，提出了一系列的改进方案[7]。Dijkstra 最短路径搜索算法的分析，从数据存储结构方面对此问题进行了探讨，并提出了一种数据文件结构，利用计算机编程，实现城市立体交通最短路径算法，实验证明该实现具有较高的效率。对空间关系，GIS开发模式，地图信息分布、存储等内容进行深入的研究。针对实际道路道路的拥堵问题，设计实现了优化路径算法，在发生交通拥塞时，找到合理的最短路径。本文的算法对以上提出的不足之处进行了改进，考虑了多种限制因素，更加贴近实际，使得实用性更强。在具体的算法实现的时候，动态的构建网络，对于一些没有用的链路，可以不进行连接，减少了路径，提高了寻找最优路径的速度。