dijkstra算法在停车诱导系统中应用

《dijkstra算法在停车诱导系统中应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Dijkstra算法在停车诱导系统中应用　　摘要：路径诱导是停车诱导系统中需要解决的关键问题，而路径诱导的本质就是求最短路径，Dijkstra算法可以很好地求解最短路径。传统Dijkstra算法采用邻接矩阵作为存储结构，算法的时间复杂度为O（n2），存在搜索速度慢和浪费空间的缺点。为此，对传统Dijkstra算法进行了改进，采用邻接多重表作为存储结构，采用堆排序法的思想来寻找权值最小的顶点，算法的时间复杂度为O（nlog2n）。用改进后的算法在实际地图中进行仿真实验，结果表明，改进后的算法能更快、更有效率地找到两点间的最短路

2、径。关键词：停车诱导系统；最短路径；Dijkstra算法；存储结构中图分类号：TP301.6文献标志码：A文章编号：1006-8228（2013）12-38-03ApplicationofDijkstraalgorithminparkingguidancesystemHuangZhen，XueWenke，LiPeng，LiJianping（DepartmentofComputerScience，HuizhouUniversity，Huizhou，Guangdong516007，China）Abstract：Therouteg

3、uidanceisthekeyproblem14intheparkingguidancesystemandtheessenceoftherouteguidanceistosettledowntheproblemoftheshortestpath.TheDijkstraalgorithmisaperfectmethodtoworkitout.ThetraditionalalgorithmappliesadjacencymatrixasitsstoragestructureanditstimecomplexityisO（n2）.

4、Howeverthiskindofalgorithmhasdisadvantagesinlowefficiencyandwastingspace.ItisimprovedbytakingadjacencymultilistasthestoragestructureandalteringthetimecomplexityintoO（nlog2n），whichhasturnedouttobemoreefficientandeffectivetofindouttheshortestpathinthesimulationexperi

5、mentofrealmap.Keywords：parkingguidancesystem；theshortestpath；Dijkstraalgorithm；storagestructure0引言14停车诱导系统是智能交通系统的一个重要组成部分，随着我国汽车产业的迅猛发展，越来越多的人开始投入到停车诱导系统方面的研究开发中。停车诱导系统中的核心问题路径诱导其实就是求解最短路径问题。目前对最短路径问题的研究有很多，在大量的最短路径算法中，Dijkstra算法是最经典的方法，有许多学者对Dijkstra算法进行优化来求解最短路径

6、问题。王树西等[1]提出了修改标记法，解决了传统Dijkstra算法的退出机制在有向图中如果两点不连通而陷入死循环的问题。章永龙[2]提出只对最短路径上节点的邻居做处理，不考虑其他节点，来减少计算节点的数量，提高算法速度。王志和等[3]提出采用配对堆结构来实现路径计算过程中优先级队列的一系列操作。王景存等[4]在Dijkstra算法基础上将决策机制运入到路径搜索中，提出一种启发式最优路径搜索算法。传统Dijkstra算法采用邻接矩阵存储结构，这在实际的交通网络上求解最短路径时，会造成空间的大量浪费，而且搜索速度慢，不能达到应

7、用的需求。本文在Dijkstra算法基础上采用邻接多重表存储结构，在实际地图中进行仿真实验，结果表明，搜索速度大大优于采用邻接矩阵的传统Dijkstra算法。1传统Dijkstra算法1.1Dijkstra算法的原理Dijkstra算法是由荷兰计算机科学家E.W.Dijkstra在1959年提出的一种求单源最短路径的算法，即选定一个起始点，计算起始点到其他点的最短路径的算法。其算法原理[5-6]如下。⑴14设有一个带权有向图G（V，E），把该图的顶点集合分成两组，一组为已经算出最短路径的顶点的集合（顶点标记为1，开始时该集合

8、为空），另一组则为还没有涉及到的顶点的集合（顶点标记为0，开始时全部顶点都标记为0）。⑵从标记为0的集合中，寻找一个距离当前中间点（初始时中间点为源顶点v0）路径最短的点作为新中间点，并标识此点为1。标记过程中，总保持从源点v0到标记为1的各个顶点的最短路径不大于从源点v0到标记为0的顶点