城市道路网最短路径启发算法研究  

Research on Urban Road Network Shortest Path Heuristic Algorithm

作　　者：刘名龙[1] 黄德镛[1] 徐天泽[2] 

机构地区：[1]昆明理工大学国土资源工程学院,云南昆明650093 [2]云南警官学院,云南昆明650223

出　　处：《公路交通科技》2006年第8期136-138,共3页Journal of Highway and Transportation Research and Development

基　　金：云南省自然科学基金资助项目(2003E0086M)

摘　　要：从城市道路网络的实际特点出发,对城市电子地图的道路网进行网络分析,将最佳路径搜索问题转化为图论中的最短路径搜索问题,通过对最短路径搜索算法的分析,提出了一种求解城市道路网两点间最短路径的算法。该算法主要对Dijkistra算法的搜索方法进行改进,根据两点间直线距离最短这一原理,运用待扩展节点与终止节点间的直线距离这一启发信息,使搜索沿着某个最有希望的路径进行下去,大大减少了搜索范围,提高了路径搜索的速度,具有重要的实践意义。With the development of geographic information science and the wide use of GIS software, there are more demand for network analyses. This paper introduces a new algorithm to get the shortest path between two points in urban road network, based on the geographic characteristic of the road network. The algorithm improved the searching way of Dijkstra＇s algorithm by making use of heuristic information to search along the most suitable path. It can greatly reduce the searching space, increase the searching speed and be of important practical significance.

关 键 词：最短路径 地理信息系统 DIJKSTRA算法 城市道路网 

分 类 号：U491.13[交通运输工程—交通运输规划与管理]