共查询到19条相似文献,搜索用时 109 毫秒
1.
Dijkstra最短路径算法改进研究及其在GIS-T仿真分析中的应用 总被引:1,自引:0,他引:1
Dijkstra算法是求解最短路径问题的经典算法,但在实际应用中还存在一些问题。提出了对传统的Dijkstra最短路径算法改进的新方法,即对复杂的公路网数据进行预处理,生成路网拓扑结构数据文件,并结合Dijkstra算法按路径长度递增次序产生最短路径的思想来求解公路网复杂线状图形的最短路径问题。 相似文献
2.
本文在分析Dijkstra算法基础上,考虑城市路网的特点及该算法在路径优化中的不足,提出一种基于双向搜索的Dijkstra改进算法,它可以减少路网节点的搜索范围和计算复杂度。仿真结果表明,改进算法在最短路径搜索中可使候选节点数减少15%~25%,当节点越多这种减少越明显,可提高搜索路径的实时性。 相似文献
3.
本文在分析Dijkstra算法基础上,考虑城市路网的特点及该算法在路径优化中的不足,提出一种基于双向搜索的Dijkstra改进算法,它可以减少路网节点的搜索范围和计算复杂度.仿真结果表明,改进算法在最短路径搜索中可使候选节点数减少15%~25%,当节点越多这种减少越明显,可提高搜索路径的实时性. 相似文献
4.
文章针对Dijkstra和Floyd算法特点及在智能运输中的特点,将两种算法结合起来,形成求解物流配送中两点间最短路径的优化算法-混合算法.该方法用Floyd计算多对顶点之间的最短路径,在路径中少数顶点之间的邻接关系发生变化时,利用Dijkstra计算这些顶点之间的最短路径,加上其余部分路径就得到该图中各对顶点之间的新的最短路径,在约束条件下最终求出各点间最短路径.实验证明,混合算法比Dijkstra及Floyd效率提高11%-20%.本文研究结果可对物流配送中最短路径的选择有所帮助. 相似文献
5.
6.
7.
首先介绍了城市交通的重要性,接着进一步阐述了Dijkstra算法及其实现在城市交通中的应用占有的重要地位。从GIS中网络最短路径算法的实际情况出发,基于MapX以及网络拓扑结构的表示与建立,以及Dijkstra算法搜索技术的实现入手,最终实现了Dijkstra最短路径算法与其在城市交通查询中的应用。本文就以经典的最短路径算法——Dijkstra算法为原理,基于MapX在VisualBasic平台对其算法研究、验证,最终得出该算法的可行性。 相似文献
8.
9.
10.
11.
最短路径分析是GIS空间分析中最基本和最关键的问题,Dijkstra算法是有效解决该问题的理论基础。本文基于GIS空间分析特征,从数据存储结构、搜索技术及网络算法本身等方面对传统Dijkstra算法进行了优化与改进,并对该算法在交通导航系统中的应用进行了探讨。 相似文献
12.
13.
VC环境下最短路径算法的实现 总被引:1,自引:0,他引:1
设计了一种方便查找及显示最短路径的数据结构,对仅研究计算一条最短路径的Dijkstra算法加以了改进,并在VC下实现一个顶点到另一个顶点的所有最短路径的查找。 相似文献
14.
The problem of finding the K shortest paths (KSPs) between a pair of nodes in a road network is an important network optimization problem with broad applications. Yen's algorithm is a classical algorithm for exactly solving the KSP problem. However, it requires numerous shortest path searches, which can be computationally intensive for real large networks. This study proposes a fast algorithm by introducing a generalized spur path reuse technique. Using this technique, shortest paths calculated during the KSP finding process are stored. Accordingly, many shortest path searches can be avoided by reusing these stored paths. The results of computational experiments on several large‐scale road networks show that the introduced generalized spur path reuse technique can avoid more than 98% of shortest path searches in the KSP finding process. The proposed algorithm speeds up Yen's algorithm by up to 98.7 times in experimental networks. 相似文献
15.
16.
17.
18.