改进Dijkstra算法在PGIS中的应用  

Application of Improved Dijkstra Algorithm in Parking Guidance Information System

作　　者：詹云[1] 孙涌[1] 房鹏[1] 

机构地区：[1]苏州大学计算机科学与技术学院,江苏苏州215006

出　　处：《计算机工程》2011年第13期193-195,共3页Computer Engineering

基　　金：国家自然科学基金资助项目(60673092)

摘　　要：传统Dijkstra算法用于路径诱导会使路网节点的数量增多、搜索范围扩大,从而耗费大量时间和空间,降低停车诱导信息系统(PGIS)的运行效率和实时性。针对城市路网的特定环境和路径诱导需求,根据2点之间直线最短的原理,在Dijkstra算法的基础上,提出一种应用于PGIS、基于矩形搜索范围的改进Dijkstra算法,设计并实现城市路网模型中单行、禁行、交叉点时间延误等问题的解决方案。实验结果表明,改进Dijkstra算法可以减少路网节点搜索范围和计算复杂度,提高用户搜索路径的实时性。When using the traditional Dijkstra algorithm for path guiding,the problems of large base number of road net node,wide searching range.With these drawbacks,much time and space are consumed.So the efficiency and real-time quality of Parking Guide Information System（PGIS） are both reduced.To solve these problems,in the light of the specific environment of city road net and the requirements of path guiding,according to the basic principle,straight line makes the shortest distance between two points,this paper puts forward a rectangular searching range based,improved Dijkstra algorithm which is applicable to PGIS.This paper designs and implements the solutions of such problems as one-way road,no passing road and cross point time delay in city road network model.Experimental results show that the improved Dijkstra algorithm not only can reduce the searching range of road net nodes and computational complexity,but also can improve the real-time quality when users searching for the path

关 键 词：停车诱导信息系统 DIJKSTRA算法 最短路径 计算复杂度 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]