共查询到15条相似文献,搜索用时 62 毫秒
1.
为使矿井避灾路线有更好的适用性,探讨了矿井面临不同类型灾害危险时最佳避灾路线分类求取方法。根据不同灾变的特点,将矿井灾害分为突水灾害,煤与瓦斯突出、瓦斯或煤尘爆炸、矿井火灾,冒顶事故三大类;绘制三类灾害的可行避灾路线拓扑图,并计算各条巷道的当量长度;将巷道当量长度作为可行路线各边的权值代入拓扑图中,用最短路径算法Dijkstra算法求解各拓扑图对应的最佳避灾路线。分析结果表明,基于Dijkstra算法的矿井最佳避灾路线分类求取方法扩大了避灾路线的选取范围,在避灾人员较多时,可使巷道系统的通行能力得以充分发挥。 相似文献
2.
扇形优化Dijkstra算法 总被引:2,自引:0,他引:2
Dijkstra算法无数次遍历所有的临时标记结点,无疑成为该算法的一个瓶颈。在分析Dijkstra算法的基础上,结合平面网络的特点,从限制搜索范围和限定搜索方向两方面着手,在扇形区域内寻找最短路径,从而完成对Dijkstra算法的优化。优化算法基于有损算法,抛弃寻找最短路径时概率较小的顶点,直接寻求在方向和位置上趋向终点的顶点。它根据用户给出的起始顶点与目标顶点以及搜索的扇形角度查找最短路径。因此,在优化算法中,频繁遍历的顶点数量大幅度减少,提高了算法的速度和运行效率。 相似文献
3.
4.
Dijkstra的一种改进算法 总被引:20,自引:3,他引:20
在Dijkstra算法的基础上,该算法使用了一些独特的数据结构(如:前趋表和最短路径表);使用该算法能高效率地求出图中一个顶点到其它各顶点的所有最短路径。用C语言设计了相应程序验证了此算法。 相似文献
5.
Dijkstra算法在GIS中的优化实现 总被引:7,自引:0,他引:7
地理信息系统(GIS)的应用经常涉及最短路径搜索问题。1959年迪杰斯特拉(Dijkstra)提出的Dijkstra算法是最适合网络拓扑中两结点间最短路径搜索的算法之一。本文讨论一般公路交通网络中两结点间的最短路径搜索问题,从核心算法方面对Dijkstra算法进行改进。 相似文献
6.
Dijkstra算法是计算最短路径的经典算法,在对该算法分析的基础上,对其进行了优化和改进。其一是对数据存储方式进行了改进,其二是对辅助向量采用堆排序改进。通过优化降低了内存消耗,搜索效率明显提高。 相似文献
7.
8.
详细介绍了Dijkstra算法,在分析Dijkstra算法的基本思想以及其缺点的基础上,提出了一种改进算法,即引入了一个标识矩阵,该算法能高效地求出一个顶点到其他各顶点的所有最短路径。并用VC++设计了相应的程序验证了此算法。 相似文献
9.
Dijkstra最短路径算法的优化及其实现 总被引:2,自引:1,他引:2
最短路径分析在地理信息系统、计算机网络路由等方面发挥了重要的作用,对其进行优化很有必要。本文分析了传统的最短路径算法(即Dijkstra算法)的优化途径及现有的优化算法,然后在Dijkstra算法的基础上,采用配对堆结构来实现路径计算过程中优先级队列的一系列操作,经理论分析与实验测试结果对比,可以大大提高该算法的效率和性能。 相似文献
10.
地理信息系统中的空间网络分析有最短路径分析、资源分配分析、等时性分析等等,而最短路径分析是其中关键的环节,因而对其算法进行优化很有必要,为此在传统的最短路径算法,即Dijkstra算法的基础上,采用二叉堆结构来实现路径计算过程中优先级队列的一系列操作,从而提高了该算法的分析效率。讨论了地理网络数据的组织结构和最短路径的具体实现过程,并引入了相关概念,并引入了相关概念,通过具体案例分析表明,改进算法在提高网络系统空间分析效率方面是可行的。 相似文献
11.
改进的Dijkstra算法在GIS路径规划中的应用 总被引:9,自引:0,他引:9
最短路径算法是计算机科学与地理信息科学等领域研究的热点。文章讨论了一种改进的Dijkstra算法,利用本算法根据用户给出的起始结点、必经点序列和目标结点在GIS的交通层网络图基础上进行路径规划,生成满足一定约束条件的最短路径。实际应用分析表明,改进的Dijkstra算法在提高网络系统空间分析效率方面是可行的。 相似文献
12.
使用Dijkstra算法搜索最短路径是地理信息系统的应用研究的一个重要组成部分。Dijkstra算法无法找到所有的最短路径,所提到的改进型算法是结合了Dijkstra算法和一定的数据结构,使得某个路径顶点到其他目标顶点的所有最短路径可以非常便捷地被找到,而且这种改进型的算法并没有增加原有算法的复杂性,故有较好的研究和实用价值。 相似文献
13.
基于Dijkstra算法的网络最短路径分析 总被引:17,自引:1,他引:17
最短路径分析是网络分析最基本的功能之一。Dijkstra算法是目前公认的较好的最短路径算法。文章通过对Dijkstra算法运行速度分析,在该算法的基础上采用二叉树结构来改进Dijkstra算法,在一定程度上优化了最短路径的计算过程,并提高了算法的分析效率,实际数据测试也表明了该算法的可行性。 相似文献
14.
GIS最短路径分析中Dijkstra算法的优化 总被引:4,自引:0,他引:4
古凌岚 《计算机与数字工程》2006,34(12):53-56
最短路径分析是GIS地理网络分析功能中的一个关键问题。Dijkstra算法是计算最短路径的经典算法,在对该算法分析的基础上,提出了基于面向对象的改进算法,大大降低了内存消耗,搜索效率明显提高。讨论了地理网络的数据存储结构和最短路径算法的具体实现,并通过实例验证表明,该算法是有效可行的。 相似文献