| 城市道路网最短路径启发算法研究 |
| |
| 引用本文： | 刘名龙,黄德镛,徐天泽.城市道路网最短路径启发算法研究[J].公路交通科技,2006,23(8):136-138. |
| |
| 作者姓名： | 刘名龙 黄德镛 徐天泽 |
| |
| 作者单位： | 1. 昆明理工大学,国土资源工程学院,云南,昆明,650093
2. 云南警官学院,云南,昆明,650223 |
| |
| 基金项目： | 云南省自然科学基金资助项目(2003E0086M) |
| |
| 摘 要： | 从城市道路网络的实际特点出发,对城市电子地图的道路网进行网络分析,将最佳路径搜索问题转化为图论中的最短路径搜索问题,通过对最短路径搜索算法的分析,提出了一种求解城市道路网两点间最短路径的算法。该算法主要对Dijkistra算法的搜索方法进行改进,根据两点间直线距离最短这一原理,运用待扩展节点与终止节点间的直线距离这一启发信息,使搜索沿着某个最有希望的路径进行下去,大大减少了搜索范围,提高了路径搜索的速度,具有重要的实践意义。
|
| 关 键 词： | 最短路径 地理信息系统 Dijkstra算法 城市道路网 |
| 文章编号： | 1002-0268(2006)08-0136-03 |
| 收稿时间： | 2005-06-25 |
| 修稿时间： | 2005年6月25日 |
Research on Urban Road Network Shortest Path Heuristic Algorithm |
| |
| LIU Ming-long,HUANG De-Yong,XU Tian-ze.Research on Urban Road Network Shortest Path Heuristic Algorithm[J].Journal of Highway and Transportation Research and Development,2006,23(8):136-138. |
| |
| Authors: | LIU Ming-long HUANG De-Yong XU Tian-ze |
| |
| Institution: | 1 . Kunming University of Science and Technology, Yunnan Kunming 650093, China; 2 , Yunnan Police Academy, Yunnan Kunming 650223, China |
| |
| Abstract: | 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. |
| |
| Keywords: | shortest path GIS Dijkstra's algorithm urban road network |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
