吉林大学学报(信息科学版) ›› 2015, Vol. 33 ›› Issue (6): 675-.

• 论文 • 上一篇    下一篇

基于GIS 的最短路径算法研究

任伟建1, 左方晨1, 黄丽杰2, 董海超3   

  1. 1. 东北石油大学电气信息工程学院, 黑龙江大庆163318; 2. 天津环球磁卡股份有限公司技术中心, 天津300202; 3. 大庆油田有限责任公司采油工程研究院, 黑龙江大庆163453
  • 收稿日期:2015-05-03 出版日期:2015-11-27 发布日期:2016-01-04
  • 作者简介:任伟建(1963—), 女, 黑龙江泰来人, 东北石油大学教授, 博士生导师, 主要从事复杂系统的建模与控制研究, (Tel)86-13845901386(E-mail)renwj@126. com。
  • 基金资助:

    国家自然科学基金资助项目(61374127); 黑龙江省博士后科研启动基金资助项目(LBH-Q12143); 黑龙江省青年科学基金资助项目(QC2013C066)

Shortest Path Algorithm Based on GIS

REN Weijian1, ZUO Fangchen1, HUANG Lijie2, DONG Haichao3   

  1. 1. School of Electrical Information & Engineering, Northeast Petroleum University, Daqing 163318, China;
    2. Technique Center, Tianjin Global Magnetic Card Company Limited, Tianjin 300202, China;
    3. Petroleum Production Engineering Research Institute, Daqing Oilfield Company Limited, Daqing 163453, China
  • Received:2015-05-03 Online:2015-11-27 Published:2016-01-04

摘要:

针对单源最短路径Dijkstra 算法效率低的问题, 基于地理信息系统(GIS: Geographic Information System),提出距离均衡的社区分析网络分割方法。将GIS 中道路网络分割降解为距离均衡的社区网络, 再利用限制分层算法, 通过淘汰不太可能出现在最短路径上的节点, 限制GIS 中最短路径的搜索区域, 以降低算法的复杂度。实验结果表明, 优化后的算法可有效减少搜索节点数, 与经典算法相比, 其运行效率有所提高。

关键词: 社区分割法, 限制分层算法, 地理信息系统, 最短路径算法

Abstract:

The monophyletic Dijkstra shortest path algorithm was analyzed based on GIS(Geographic Information System) platform. A balanced community analysis network segmentation method was proposed, the road network was divided and degraded into balanced community network based on GIS, and the limited layering algorithm was used. Nodes that are unlikely to appear on the optimal path was eliminated to limit the search area and the purpose of reducing the complexity of algorithm is achieved. The experiments show that the optimized results can effectively reduce the number of searching nodes, compared with the classic algorithms, the efficiency is improved.

Key words: community segmentation algorithm, limit layered algorithm, geographic information system(GIS);
shortest path algorithm

中图分类号: 

  • TP311. 11