|
|||||
|
|
| 基于GIS 的最短路径算法研究 | |
| 引用本文： | 任伟建,左方晨,黄丽杰,董海超.基于GIS 的最短路径算法研究[J].吉林大学学报(信息科学版),2015,33(6):675-679. |
| 作者姓名： | 任伟建 左方晨 黄丽杰 董海超 |
| 作者单位： | 1. 东北石油大学电气信息工程学院, 黑龙江大庆163318; 2. 天津环球磁卡股份有限公司技术中心, 天津300202; 3. 大庆油田有限责任公司采油工程研究院, 黑龙江大庆163453 |
| 基金项目： | 国家自然科学基金资助项目(61374127)，黑龙江省博士后科研启动基金资助项目(LBH-Q12143)，黑龙江省青年科学基金资助项目(QC2013C066) |
| 摘 要： | 针对单源最短路径Dijkstra 算法效率低的问题, 基于地理信息系统(GIS: Geographic Information System),提出距离均衡的社区分析网络分割方法。将GIS 中道路网络分割降解为距离均衡的社区网络, 再利用限制分层算法, 通过淘汰不太可能出现在最短路径上的节点, 限制GIS 中最短路径的搜索区域, 以降低算法的复杂度。实验结果表明, 优化后的算法可有效减少搜索节点数, 与经典算法相比, 其运行效率有所提高。 |
| 关 键 词： | 社区分割法 限制分层算法 地理信息系统 最短路径算法 |
| 收稿时间： | 2015-05-03 |
Shortest Path Algorithm Based on GIS |
|
| REN Weijian,ZUO Fangchen,HUANG Lijie,DONG Haichao.Shortest Path Algorithm Based on GIS[J].Journal of Jilin University:Information Sci Ed,2015,33(6):675-679. | |
| Authors: | REN Weijian ZUO Fangchen HUANG Lijie DONG Haichao |
| Institution: | 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 |
| 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. |
| Keywords: | community segmentation algorithm limit layered algorithm geographic information system(GIS) shortest path algorithm |
| 本文献已被 万方数据 等数据库收录！ | |
| 点击此处可从《吉林大学学报(信息科学版)》浏览原始摘要信息 | |
| 点击此处可从《吉林大学学报(信息科学版)》下载免费的PDF全文 | |