|Table of Contents|

Improved Shortest Path Algorithm for Restricted Searching Area

《南京理工大学学报》(自然科学版)[ISSN:1005-9830/CN:32-1397/N]

Issue:
2009年05期
Page:
638-642
Research Field:
Publishing date:

Info

Title:
Improved Shortest Path Algorithm for Restricted Searching Area
Author(s):
WANG Hai-mei1ZHOU Xian-zhong2
1.School of Automation,NUST,Nanjing 210094,China;2.Department of Control and Systems Engineering,Nanjing University,Nanjing 210093,China
Keywords:
shortest path Dijkstra algorithm restricted rectangle searching area ratio coefficients
PACS:
TP301.6
DOI:
-
Abstract:
Algorithmic efficiency of the shortest path searching is a problem which has brought wide attention and needs to be resolved urgently in many application fields.Based on the classical Dijkstra’s shortest path algorithm,the optimization means is analyzed.A restricted rectangle searching area algorithm is proposed to reduce the searching area.In order to improve the running efficiency,variational ratio coefficients are used during path searching to adapt the characteristic of the road network path searching.The experiment on the prototype system shows that the algorithm presented here is highly effective and feasible.

References:

[ 1] 乐阳, 龚健雅. Dijkstra最短路径算法的一种高效率实现[ J]. 武汉测绘科技大学学报, 1999, 24( 3): 209-212.
[ 2] 王开义, 赵春江, 胥桂仙, 等. GIS领域最短路径搜索问题的一种高效实现[ J]. 中国图象图形学报, 2003, 8( 8): 951- 956.
[ 3] 陆锋, 卢冬梅, 崔伟宏. 交通网络限制搜索区域时间最短路径算法[ J]. 中国图象图形学报, 1999, 4( 10): 849-853.
[ 4] 陈则王, 袁信. 基于分层分解的一种实时车辆路径规划算法[ J]. 南京航空航天大学学报, 2003, 35( 2): 193-197.
[ 5] Hart P, NilssonN, PaphaelB. A formal basis for the heuristic determination of minimum cost path[ J]. IEEETransactions onSystemsScience andCyberne-t ics, 1968, 4( 2): 100-107.
[ 6] 陆锋, 周成虎, 万庆. 基于层次空间推理的交通网络行车最优路径算法[ J]. 武汉测绘科技大学学报, 2000, 25(3): 226- 232.
 [ 7] Fisher PF. Aprimer ofgeographic searchusing artif-i cial intelligence[ J]. Computers and Geosciences, 1990, 16( 6): 753-776.
[ 8] 严寒冰,刘迎春. 基于GIS的城市道路网最短路径算法探讨[ J]. 计算机学报, 2000, 23( 2): 210-215.
[ 9] 陆锋, 卢冬梅,崔伟宏. 基于四叉堆优先级队列及逆邻接表的改进型Dijkstra算法[ J]. 中国图象图形学报, 1999, 4( 12): 1044-1050.
[ 10] 唐文武, 施晓东, 朱大奎. GIS中使用改进的Dijk-stra算法实现最短路径的计算[ J]. 中国图象图形学报, 2000, 5( 12): 1019-1023.
[ 11] StigN, BengtR. Computer cartography shortest route program[M]. Sweden: TheRoyalUniversity ofLund, 1969.
[ 12] 崔伟宏. 空间数据结构研究[M]. 北京: 中国科学技术出版社, 1995.
[ 13] 陈行星, 崔伟宏. 城市快速反应系统实验研究[ J]. 环境遥感, 1995, 11( 3): 227- 233.
[ 14] 王海梅, 周献中. 网络系统中的最短路径分析及其应用研究[ J]. 兵工学报, 2006, 27(3): 515- 518.

Memo

Memo:
-
Last Update: 2012-11-19