作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2011, Vol. 37 ›› Issue (13): 193-195. doi: 10.3969/j.issn.1000-3428.2011.13.062

• 人工智能及识别技术 • 上一篇    下一篇

改进Dijkstra算法在PGIS中的应用

詹 云,孙 涌,房 鹏   

  1. (苏州大学计算机科学与技术学院,江苏 苏州 215006)
  • 收稿日期:2011-02-11 出版日期:2011-07-05 发布日期:2011-07-05
  • 作者简介:詹 云(1985-),女,硕士研究生,主研方向:智能交通系统;孙 涌,副教授;房 鹏,硕士研究生
  • 基金资助:
    国家自然科学基金资助项目(60673092)

Application of Improved Dijkstra Algorithm in Parking Guidance Information System

ZHAN Yun, SUN Yong, FANG Peng   

  1. (College of Computer Science and Technology, Soochow University, Suzhou 215006, China)
  • Received:2011-02-11 Online:2011-07-05 Published:2011-07-05

摘要: 传统Dijkstra算法用于路径诱导会使路网节点的数量增多、搜索范围扩大,从而耗费大量时间和空间,降低停车诱导信息系统(PGIS)的运行效率和实时性。针对城市路网的特定环境和路径诱导需求,根据2点之间直线最短的原理,在Dijkstra算法的基础上,提出一种应用于PGIS、基于矩形搜索范围的改进Dijkstra算法,设计并实现城市路网模型中单行、禁行、交叉点时间延误等问题的解决方案。实验结果表明,改进Dijkstra算法可以减少路网节点搜索范围和计算复杂度,提高用户搜索路径的实时性。

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

Abstract: 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.

Key words: Parking Guidance Information System(PGIS), Dijkstra algorithm, shortest path, calculation complexity degree

中图分类号: