摘要
路径诱导是停车诱导系统中需要解决的关键问题,而路径诱导的本质就是求最短路径,Dijkstra算法可以很好地求解最短路径。传统Dijkstra算法采用邻接矩阵作为存储结构,算法的时间复杂度为O(n2),存在搜索速度慢和浪费空间的缺点。为此,对传统Dijkstra算法进行了改进,采用邻接多重表作为存储结构,采用堆排序法的思想来寻找权值最小的顶点,算法的时间复杂度为O(nlog2n)。用改进后的算法在实际地图中进行仿真实验,结果表明,改进后的算法能更快、更有效率地找到两点间的最短路径。
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.
出处
《计算机时代》
2013年第12期38-41,共4页
Computer Era
基金
惠州市科技计划项目(No.2012-10)
广东省大学生创新训练项目(105771300)
