基于GIS的Dijkstra算法改进研究

作者：任伟建; 左方晨; 黄丽杰

来源：控制工程, 2018, 25(02): 188-191.

DOI：10.14107/j.cnki.kzgc.150340

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

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

• 单位
  中海油天津化工研究设计院有限公司; 东北石油大学; 天津环球磁卡股份有限公司