基于GIS的Dijkstra算法改进研究

任伟建, 左方晨, 黄丽杰

控制工程 ›› 2018, Vol. 25 ›› Issue (2) : 188-191.

控制工程 ›› 2018, Vol. 25 ›› Issue (2) : 188-191.

基于GIS的Dijkstra算法改进研究

作者信息 +

The Improvement Research of Dijkstra Algorithm Based on GIS

Author information +
文章历史 +

摘要

基于地理信息系统(GIS),针对单源最短路径Dijkstra算法效率低的问题,利用网络分割法将社区中与外界有边连接的节点作为社区代表点,以减少节点数量,降低问题求解的规模。将复杂的道路网络降解为简单道路网络,从而提高搜索效率。并结合人工势场法,计算源点到目标点的势场强度。通过临时节点与源点、目标点的势场强度和的比较,使搜索沿着一定方向进行,减少Dijkstra算法中的搜索范围。实验表明,优化后的结果可以有效提高搜索效率。

Abstract

Based on the geographic information system (GIS), aimed at the problems of single source shortest path Dijkstra algorithm’s low efficiency, the nodes connected to the outside world in a community are used as the community representative points through the network partition method, so as to reduce the number of nodes and the scale of problem solving. The complex road network is degraded into a simple road network to improve the search efficiency. Combined with the artificial potential field method, the potential field intensity of the source point to the target point is calculated. By comparing the intensity of the potential field of the temporary node, the source point and the target point, the search is carried out in a certain direction, and the search range in the Dijkstra algorithm is reduced. Experiments show that the optimized results can effectively improve the search efficiency.

关键词

网络分割 / Dijksta算法 / 人工势场法

Key words

Network partition / Dijksta algorithm / artificial potential

引用本文

导出引用
任伟建, 左方晨, 黄丽杰.

基于GIS的Dijkstra算法改进研究 [J]. 控制工程, 2018, 25(2): 188-191

REN Wei-jian, ZUO Fang-chen, Huang Li-jie. The Improvement Research of Dijkstra Algorithm Based on GIS[J]. Control Engineering of China, 2018, 25(2): 188-191

基于GIS的Dijkstra算法改进研究" title="Share on Weibo" target="_blank">

4

Accesses

0

Citation

Detail

段落导航
相关文章

/