城市道路最短路径的Dijkstra算法优化 被引量：48

1

作者 张渭军 王华 《长安大学学报（自然科学版）》 EI CAS CSCD 北大核心 2005年第6期62-65,共4页

在研究城市道路网络特征基础上,建立城市道路网络模型及其数据库,应用一种改进的Dijkstra算法对城市道路进行最短路径查询,该算法是从起点和终点分别用二叉树按起点到终点和终点到起点的方向进行搜索。在计算某一段最短路径时,用Dijkstr... 在研究城市道路网络特征基础上,建立城市道路网络模型及其数据库,应用一种改进的Dijkstra算法对城市道路进行最短路径查询,该算法是从起点和终点分别用二叉树按起点到终点和终点到起点的方向进行搜索。在计算某一段最短路径时,用Dijkstra算法时间为0.23 s,改进算法时间为0.20 s。仿真结果表明,该算法不仅在时间上有所改进,其时间复杂度由传统Dijkstra算法的O(n2)减小为O(n),而且其所选的最优路径更符合实际,是一种寻求最优路径的有效算法。 展开更多

关键词 交通工程 道路网络 数据库 dijkstra算法 最短路径 二叉树

下载PDF 职称材料

嵌入式GIS最短路径分析中Dijkstra法改进 被引量：23

2

作者 王宏勇 卢战伟 《测绘学院学报》 北大核心 2005年第1期43-45,共3页

Dijkstra算法是求解网络中最短路径的精典算法,文中通过改变图的存储结构及搜索方法,减少了内存存储空间,缩短查询时间,以提高该算法在嵌入式GIS系统中路径优化的效率。

关键词 最短路径分析 dijkstra算法 嵌入式GIS

下载PDF 职称材料

交通限制条件下城市物流配送路线优化选择 被引量：13

3

作者 朱永升 韩伯棠 +1 位作者 夏平 李振键 《武汉理工大学学报（交通科学与工程版）》 北大核心 2004年第3期391-394,共4页

物流配送网络中最优路线的选择问题一直都是配送中心关注的焦点 ,对于长途配送而言 ,交通阻塞和道路拥堵状况可以忽略不计 ,但对于城市配送而言 ,由于受交通堵塞和各种交通管制的影响 ,导致配送路径寻优更具复杂性 .文中通过对具有动态... 物流配送网络中最优路线的选择问题一直都是配送中心关注的焦点 ,对于长途配送而言 ,交通阻塞和道路拥堵状况可以忽略不计 ,但对于城市配送而言 ,由于受交通堵塞和各种交通管制的影响 ,导致配送路径寻优更具复杂性 .文中通过对具有动态的交通堵塞和交通拥挤限制信息及静态禁止通行等限制信息的实际配送网络的描述 ,提出解决两种限制情况下配送网络寻优的方法 ,建立了配送网络图中权重确定模型 ,并提出将交通限制条件下城市物流配送网络转化成无限制的有向图网络 ,运用 Dijkstra算法对其寻优 。 展开更多

关键词 物流配送 成本系数 dijkstra算法

下载PDF 职称材料

基于监测覆盖范围的瓦斯传感器无盲区布置 被引量：20

4

作者 孙继平 唐亮 +3 位作者 陈伟 张博 朱宁 张向阳 《煤炭学报》 EI CAS CSCD 北大核心 2008年第8期946-950,共5页

通过建立矿井通风网络的图论模型,提出将监测范围作为传感器部署的理论依据,以节点间风流流经时间作为监测等级,应用覆盖度作为优选最佳测点标准,基于D ijkstra算法和极小支配集算法求得传感器的最佳布点.以一小型矿井通风网络为例,求... 通过建立矿井通风网络的图论模型,提出将监测范围作为传感器部署的理论依据,以节点间风流流经时间作为监测等级,应用覆盖度作为优选最佳测点标准,基于D ijkstra算法和极小支配集算法求得传感器的最佳布点.以一小型矿井通风网络为例,求解瓦斯传感器的最优布点,结果表明监测等级不同对应的安全等级也不同,布点的数量、位置以及监测覆盖度也不同. 展开更多

关键词 瓦斯传感器 图论 dijkstra算法 极小支配集

下载PDF 职称材料

智能交通系统中Dijkstra算法的高效实现 被引量：16

5

作者 王元彪 《计算机工程》 CAS CSCD 北大核心 2007年第6期256-258,261,共4页

在智能交通系统中,最佳路径和最短路径的计算是车辆导航功能重要环节,由于越来越多的实时信息参与计算,使得计算行车时间最短的路径变得更频繁,加上道路网络的结点数量和路段数量多,因此,对算法的效率也就要求更高。目前最常用的最佳路... 在智能交通系统中,最佳路径和最短路径的计算是车辆导航功能重要环节,由于越来越多的实时信息参与计算,使得计算行车时间最短的路径变得更频繁,加上道路网络的结点数量和路段数量多,因此,对算法的效率也就要求更高。目前最常用的最佳路径/最短路径算法之一是Dijkstra算法。在智能交通系统中,通过建立相关的数据索引表,可以高效地实现Dijkstra算法,与原始算法相比,大大提高了效率。 展开更多

关键词 dijkstra算法 最佳路径 智能交通 车辆导航

下载PDF 职称材料

地理信息系统中算法的研究 被引量：10

6

作者 田杰 吴力合 吕建新 《微计算机信息》 2003年第7期92-93,共2页

我们开发的地理信息系统,可根据查询对象的不同标注出铁路、公路、水路和航空交通网,并可按任意比例缩放,其核心功能是任意选择的两个城市,采用Dijkstra迪杰斯特拉算法,可求出两者之间的最佳路径。本文对该数模的建立及其算法做了详细... 我们开发的地理信息系统,可根据查询对象的不同标注出铁路、公路、水路和航空交通网,并可按任意比例缩放,其核心功能是任意选择的两个城市,采用Dijkstra迪杰斯特拉算法,可求出两者之间的最佳路径。本文对该数模的建立及其算法做了详细的论述。 展开更多

关键词 地理信息系统 数学模型 算法 迪杰斯特拉算法 dijkstra算法

下载PDF 职称材料

在MapInfo电子地图中搜寻最短路径的实现 被引量：5

7

作者 阮曹华 徐绪忠 +1 位作者 李华贵 孔若英 《微计算机信息》 北大核心 2007年第28期189-190,246,共3页

根据MapInfo电子地图的特点,本文介绍了如何从电子地图中提取出交通道路及道路交汇点信息,并将其抽象成图,选择合适的结构进行存储,然后运用Dijkstra最短路径算法求解最短路径,根据求解结果在电子地图上绘制线路图。

关键词 最短路径搜寻 MapInfo电子地图 dijkstra算法 地理信息系统

下载PDF 职称材料

嵌入式GIS最短路径分析中Dijkstra算法的改进 被引量：7

8

作者 王玉琨 吴锋 《计算机工程与应用》 CSCD 北大核心 2008年第28期128-129,共2页

Dijkstra算法是求解网络中最短路径的经典算法,文中通过改变图的存储结构及搜索方法,减少了内存存储空间,缩短了查询时间,以提高该算法在嵌入式GIS(Geographic Information System)系统中路径优化的效率。并将该算法应用在嵌入式焦作市... Dijkstra算法是求解网络中最短路径的经典算法,文中通过改变图的存储结构及搜索方法,减少了内存存储空间,缩短了查询时间,以提高该算法在嵌入式GIS(Geographic Information System)系统中路径优化的效率。并将该算法应用在嵌入式焦作市地理信息公众查询系统中,取得满意的效果。 展开更多

关键词 最短路径分析 dijkstra算法 嵌入式

下载PDF 职称材料

基于时间Petri网的电力系统故障恢复算法的研究 被引量：5

9

作者 刘春颖 李月乔 文亚凤 《系统仿真学报》 CAS CSCD 北大核心 2007年第A01期254-258,共5页

随着电网建设的逐步升级和加强,电网结构趋于成熟稳定,但也愈加庞大复杂。电网不可避免受到故障影响而导致停电,严重危害社会经济的持续发展,因此,电力系统故障恢复问题的研究正成为完善电网建设的一项重要任务。时间Petri网是一种用于... 随着电网建设的逐步升级和加强,电网结构趋于成熟稳定,但也愈加庞大复杂。电网不可避免受到故障影响而导致停电,严重危害社会经济的持续发展,因此,电力系统故障恢复问题的研究正成为完善电网建设的一项重要任务。时间Petri网是一种用于描述系统动态行为和分析系统动态性质的数学模型,对描述和分析并发现象有其独到的优越之处,非常适合于异步并发系统的建模。用时间Petri网来解决故障恢复是一种新型算法。根据时间Petri网的特点,利用时间Petri网为配电网典型结构建立模型,应用迪杰斯特拉计算机算法,辅助计算电力系统配电网故障恢复的最优路径。举例验证本算法的有效性。 展开更多

关键词 电力系统 事故恢复 时间PETRI网 迪杰斯特拉算法

下载PDF 职称材料

基于物流配送系统的运输路径分析及应用 被引量：3

10

作者 宁青香 宋娜 宁书年 《苏州科技学院学报（自然科学版）》 CAS 2006年第4期74-79,共6页

物流配送系统中运输路径的优化研究对于节约物流成本、提高物流效率有着重要的意义。经典Dijkstra算法在求解最短网络中两点间最短路径时,需要计算大量与最短路径无关的结点间的路径,占用了大量计算机的内存。本文在此基础上提出了改进... 物流配送系统中运输路径的优化研究对于节约物流成本、提高物流效率有着重要的意义。经典Dijkstra算法在求解最短网络中两点间最短路径时,需要计算大量与最短路径无关的结点间的路径,占用了大量计算机的内存。本文在此基础上提出了改进算法,该算法避免使用含有大量无穷值的关联矩阵,节省了内存,使之更适合处理带有拐向限制和包含大量结点信息的最短路径问题。 展开更多

关键词 物流配送 最短路径 dijkstra算法 最大相邻结点算法

下载PDF 职称材料

集装箱堆场起重机行驶成本研究 被引量：2

11

作者 王剑栩 孙小明 《起重运输机械》 北大核心 2006年第6期46-49,共4页

针对国内多数集装箱堆场采用先到先服务的服务规则造成起重机迂回行驶现象严重的情况,提出运用Dijkstra算法和最短路径法的综合方法安排起重机作业。介绍了Dijkstra算法,建立了堆场起重机行驶成本模型,针对实际操作中的动态现象运用启... 针对国内多数集装箱堆场采用先到先服务的服务规则造成起重机迂回行驶现象严重的情况,提出运用Dijkstra算法和最短路径法的综合方法安排起重机作业。介绍了Dijkstra算法,建立了堆场起重机行驶成本模型,针对实际操作中的动态现象运用启发式算法中最短路径法来安排起重机服务堆列,通过一个案例来说明该综合方法的使用,并通过仿真对该综合方法和先到先服务的方法进行比较,得到较优的方法,使起重机的行驶成本下降。 展开更多

关键词 集装箱堆场起重机 dijkstra算法 最短路径法 行驶成本 排队规则

下载PDF 职称材料

Dijkstra算法在后勤补给运输中的应用及其优化 被引量：4

12

作者 官斌 马焱 《舰船电子工程》 2011年第8期140-142,共3页

文章在分析传统Dijkstra算法的基础上,针对传统Dijkstra算法存在的两点不足之处,引入了一种优化算法。当后勤补给运输的网络规模较大及其关联矩阵为一个稀疏矩阵时,以上优化算法与传统Dijkstra算法相比,能大大减少计算次数及比较次数,... 文章在分析传统Dijkstra算法的基础上,针对传统Dijkstra算法存在的两点不足之处,引入了一种优化算法。当后勤补给运输的网络规模较大及其关联矩阵为一个稀疏矩阵时,以上优化算法与传统Dijkstra算法相比,能大大减少计算次数及比较次数,提高运算效率。 展开更多

关键词 dijkstra算法 后勤补给运输 优化

下载PDF 职称材料

城市道路交通网中最短路径搜索算法设计及其实现 被引量：3

13

作者 康志瑜 王明生 《国防交通工程与技术》 2005年第1期57-59,62,共4页

交通网络中最短路径的搜索是地理信息科学与计算机科学等领域的研究热点。本文以石家庄市中心区域部分道路网为实践对象,结合道路网络的特点,在自定义节点-链拓扑结构表达路网的基础上,提出了一种适于最短路径算法的空间数据组织方式,... 交通网络中最短路径的搜索是地理信息科学与计算机科学等领域的研究热点。本文以石家庄市中心区域部分道路网为实践对象,结合道路网络的特点,在自定义节点-链拓扑结构表达路网的基础上,提出了一种适于最短路径算法的空间数据组织方式,运用迪杰斯特拉(Dijkstra)最短路径算法,以MapInfo的二次开发语言MapBasic为开发工具,在电子地图环境下实现了道路网络中任意两节点间最短路径的快速解算与刷新显示。 展开更多

关键词 城市道路交通网 最短路径搜索 算法设计 MAPBASIC 最短路径算法 MapInfo 地理信息科学 数据组织方式 二次开发语言 道路网络 计算机科学 研究热点 交通网络 中心区域 石家庄市 结构表达 开发工具 快速解算 电子地图 自定义

下载PDF 职称材料

城市供水管网优化设计两步法 被引量：5

14

作者 张世泽 袁一星 李玉华 《哈尔滨工业大学学报》 EI CAS CSCD 北大核心 2009年第4期111-117,共7页

为改善城市供水管网的设计方案,从经济性和可靠性角度出发,应用数学建模与最优化理论,对城市供水管网优化设计进行系统研究.提出两步优化的思想,即首先进行供水管网拓扑结构优化,然后进行管径组合方案优化.供水管网拓扑结构优化以单位... 为改善城市供水管网的设计方案,从经济性和可靠性角度出发,应用数学建模与最优化理论,对城市供水管网优化设计进行系统研究.提出两步优化的思想,即首先进行供水管网拓扑结构优化,然后进行管径组合方案优化.供水管网拓扑结构优化以单位流量年计算费用作为管段的权值,采用改进的狄克斯特拉算法进行求解,管径组合方案优化采用遗传算法进行求解.分别编制相应计算程序,对某一管网进行优化设计.研究结果表明由该方法产生的优化设计方案在经济性、水力性和可靠性方面均好于传统设计方案,同时两步优化的解无论在收敛速度方面还是在解的优化效果方面都要好于单纯应用遗传算法所求得的解. 展开更多

关键词 供水管网 优化设计 可靠性 遗传算法 管网拓扑结构 狄克斯特拉算法

下载PDF 职称材料

车流去向查询实现算法

15

作者 毛思晨 《铁路计算机应用》 2004年第6期10-12,共3页

提出一种基于基点基线法计算最短径路里程的车流去向查询算法:全面分析货运列车的行走规律,利用图论中基点基线的概念,将全国货运路网图按照点、线相关的编码规则划分,以适应Dijkstra算法基本思想,并在此基础上提出等代价Dijkstra算法... 提出一种基于基点基线法计算最短径路里程的车流去向查询算法:全面分析货运列车的行走规律,利用图论中基点基线的概念,将全国货运路网图按照点、线相关的编码规则划分,以适应Dijkstra算法基本思想,并在此基础上提出等代价Dijkstra算法搜索最短里程径路计算的数学模型。将查找车流径路问题转化为寻求发站、车流径路和到站之间的最短径路问题,实现车流去向查询。 展开更多

关键词 车流去向查询算法 最短径路里程 贷运列车 图论 基点基线法 车流径路 等代价dijkstra算法

下载PDF 职称材料

Internet中常用路由选择算法分析

16

作者 傅茂忠 高茂庭 《电脑知识与技术》 2009年第6期4180-4181,4183,共3页

该文主要介绍用于Internet路由选择的两种常用算法：Dijkstra算法和Bellman-Ford算法，以及对这两种算法优缺点进行分析．并提出了解决这两种算法问题的改进思路。

关键词 路由选择 dijkstra算法 Bellman—Ford算法 最短路径

下载PDF 职称材料

Dijkstra算法在城市道路网络中的应用 被引量：1

17

作者 渠寒花 王丽娜 周杰 《电脑知识与技术（过刊）》 2007年第22期984-986,共3页

本文介绍了一个利用自然语言处理技术进行城市交通查询的系统.在研究城市道路网络特征基础上,建立城市道路网络模型及其数据库,应用Dijkstra算法对城市道进行最短路径查询,该算法是从起点和终点分别用二叉树按起点到终点和终点到起点的... 本文介绍了一个利用自然语言处理技术进行城市交通查询的系统.在研究城市道路网络特征基础上,建立城市道路网络模型及其数据库,应用Dijkstra算法对城市道进行最短路径查询,该算法是从起点和终点分别用二叉树按起点到终点和终点到起点的方向进行搜索,并得到良好的查询结果. 展开更多

关键词 交通网络 数据库 dijkstra算法 最短路径

下载PDF 职称材料

城市道路最短路径算法的研究

18

作者 杨天石 刘晓东 于小平 《长春工程学院学报（自然科学版）》 2006年第2期57-59,共3页

建立城市公交最短路径有利于城市交通建设有序和稳定的发展,目前采用GIS技术可以有效地管理公交车辆。从系统的最短路径入手,对行走路线作了分析,并给出了用于空间分析的最短路径追踪方法。此外介绍了该系统在具体城市交通应用中所要遵... 建立城市公交最短路径有利于城市交通建设有序和稳定的发展,目前采用GIS技术可以有效地管理公交车辆。从系统的最短路径入手,对行走路线作了分析,并给出了用于空间分析的最短路径追踪方法。此外介绍了该系统在具体城市交通应用中所要遵循的原则。 展开更多

关键词 最短路径 dijkstra算法 GIS MAPOBJECT

下载PDF 职称材料

谈重大危险源信息管理系统的城市安全控制 被引量：1

19

作者 柳俊 《武汉船舶职业技术学院学报》 2011年第3期66-68,72,共4页

本文首先阐述重大危险源的概念,重大危险源系统的组成,然后结合重大危险源信息管理系统,介绍了对重大危险源的辨识和控制技术,以及当危险源事故发生时的事故预案的方法,最后还提出了相关的解决方案。

关键词 重大危险源信息系统 dijkstra算法

下载PDF 职称材料

基于移动定位信息的最短路径搜索算法

20

作者 胡明 赵婉婷 《电脑知识与技术（过刊）》 2009年第11X期9030-9031,9049,共3页

该文利用改进的Dijkstra算法求出车辆行驶的最短路径,并根据道路限定的车速,交通异常信息等对所求的最短路径进行分析,最终得到所用时间和距离最短的最短路径。

关键词 dijkstra算法 最短路径 交通异常信息

下载PDF 职称材料