基于GIS的Dijkstra算法改进研究  

The Improvement Research of Dijkstra Algorithm Based on GIS

作　　者：任伟建[1,2] 左方晨 黄丽杰 

机构地区：[1]东北石油大学电气信息工程学院,黑龙江大庆163318 [2]黑龙江省网络化与智能控制重点实验室,黑龙江大庆163318 [3]中海油天津化工研究设计院有限公司,天津300131 [4]天津环球磁卡股份有限公司,天津300202

出　　处：《控制工程》2018年第2期188-191,共4页Control Engineering of China

基　　金：国家自然基金(61374127);黑龙江省博士后科研启动资金(LBH-Q12143)

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

分 类 号：TP311.11[自动化与计算机技术—计算机软件与理论]