首页 | 本学科首页   官方微博 | 高级检索  
     

Dijkstra算法在停车诱导系统中的应用
引用本文:黄震,薛文科,李鹏,李剑平.Dijkstra算法在停车诱导系统中的应用[J].计算机时代,2013(12):38-41.
作者姓名:黄震  薛文科  李鹏  李剑平
作者单位:惠州学院计算机科学系
基金项目:惠州市科技计划项目(No.2012-10);广东省大学生创新训练项目(105771300)
摘    要:路径诱导是停车诱导系统中需要解决的关键问题,而路径诱导的本质就是求最短路径,Dijkstra算法可以很好地求解最短路径.传统Dijkstra算法采用邻接矩阵作为存储结构,算法的时间复杂度为O(n2),存在搜索速度慢和浪费空间的缺点.为此,对传统Dijkstra算法进行了改进,采用邻接多重表作为存储结构,采用堆排序法的思想来寻找权值最小的顶点,算法的时间复杂度为O(nlog2n).用改进后的算法在实际地图中进行仿真实验,结果表明,改进后的算法能更快、更有效率地找到两点间的最短路径.

关 键 词:停车诱导系统  最短路径  Dijkstra算法  存储结构

Application of Dijkstra algorithm in parking guidance system
Huang Zhen;Xue Wenke;Li Peng;Li Jianping.Application of Dijkstra algorithm in parking guidance system[J].Computer Era,2013(12):38-41.
Authors:Huang Zhen;Xue Wenke;Li Peng;Li Jianping
Affiliation:Huang Zhen;Xue Wenke;Li Peng;Li Jianping;Department of Computer Science, Huizhou University;
Abstract:The route guidance is the key problem in the parking guidance system and the essence of the route guidance is to settle down the problem of the shortest path. The Dijkstra algorithm is a perfect method to work it out. The traditional algorithm applies adjacency matrix as its storage structure and its time complexity is O(n2). However this kind of algorithm has disadvantages in low efficiency and wasting space. It is improved by taking adjacency multilist as the storage structure and altering the time complexity into O(nlog2n), which has turned out to be more efficient and effective to find out the shortest path in the simulation experiment of real map.
Keywords:parking guidance system  the shortest path  Dijkstra algorithm  storage structure
本文献已被 CNKI 维普 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号