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

任偉建，左方晨，黃麗杰，董海超

(1.東北石油大學電氣信息工程學院，黑龍江大慶163318;2.天津環球磁卡股份有限公司技術中心，天津300202; 3.大慶油田有限責任公司采油工程研究院，黑龍江大慶163453)

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

任偉建1，左方晨1，黃麗杰2，董海超3

(1.東北石油大學電氣信息工程學院，黑龍江大慶163318;2.天津環球磁卡股份有限公司技術中心，天津300202; 3.大慶油田有限責任公司采油工程研究院，黑龍江大慶163453)

針對單源最短路徑Dijkstra算法效率低的問題，基于地理信息系統(GIS:Geographic Information System)，提出距離均衡的社區分析網絡分割方法。將GIS中道路網絡分割降解為距離均衡的社區網絡，再利用限制分層算法，通過淘汰不太可能出現在最短路徑上的節點，限制GIS中最短路徑的搜索區域，以降低算法的復雜度。實驗結果表明，優化后的算法可有效減少搜索節點數，與經典算法相比，其運行效率有所提高。

社區分割法;限制分層算法;地理信息系統;最短路徑算法

0 引 言

隨著計算機系統和地理信息科學的迅猛發展，地理信息系統［1］(GIS:Geographical Information System)逐漸深入到各個專業領域和百姓生活中。而最短路徑問題是GIS中最基本、最關鍵的問題，與人們的日常生活聯系緊密，如導航、公交查詢、應急搶險和物流運輸等［2］。

目前，求解最短路徑的算法很多，較常見的有經典圖論法［3］、啟發搜索方法［4］、動態規劃法［5］和人工算法等［6］。A*算法是常用的啟發式搜索方法，但由于其執行時間長(指數級)，故很少采用;動態規劃法能有效解決多階段決策問題，但需要以大量的階段性狀態信息為基礎，故該算法主要用于小型試驗級網絡的最短路徑計算。……