矢量地图中一种求最短路径的快速算法
开篇：润墨网以专业的文秘视角，为您筛选了一篇矢量地图中一种求最短路径的快速算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘 要：在分析总结了经典Dijkstra算法的基础上，提出了求最短路径的一种快速实现算法，根据算法的复杂度与网络节点数n成线性关系即O（n）的特点，给出了该算法的具体实现结构。
关键词：最短路径算法;城市道路网络;地理信息系统;经典Dijkstra算法
中图分类号：TP391 文献标识码：A 文章编号：2095-1302（2015）09-00-03
0 引 言
最短路径问题（SP）是最基本的网络优化问题之一，在交通网络分析系统中占有重要地位，是其它网络优化算法的基础。最短路径问题在实际中常用于汽车导航系统以及各种应急系统，这些系统一般要求到目的地的最佳路线所用时间尽可能短，并且要求根据交通状况进行实时计算。经典的最短路径算法――Dijkstra算法是目前多数系统解决最短路径问题采用的理论基础，不同系统对Dijkstra算法采用了不同的实现方法。本文以经典Dijkstra算法为理论基础，在对矢量地图进行大量分析、实验的基础上，提出最短路径的一种快速实现算法，算法的复杂度与网络节点数n成线性关系，即O（n），与经典Dijkstra算法的O（n2）相比，提高了算法的实用性。
1.1 经典Dijkstra算法的主要思想
Dijkstra算法的基本思路是：假设每个点都有一对标号（dj ， pj），其中dj是从源点s到点j的最短路径的长度（不包括顶点到其本身）;pj则是从s到j的最短路径中j点的前一点，k为已标记节点的集合。求解从源点s到点j的最短路径算法的基本过程如下：
（1）初始化。源点设置为：ds=0，ps为空;所有其它点：di=∞，pi=？;标记源点s，记k ={s}，其他所有点设为未标记。
（2）检验从所有已标记的点k到其直接连接的未标记的点j的距离，并设置：dj=min[dj，dk+lkj]，其中，lkj是从点k到j的直接连接距离。
（3）选取下一个点。从所有未标记的结点中，选取dj中最小的一个i：di=min[dj，所有未标记的点j]，点i就被选为最短路径中的一点，并设为已标记的。
（4）找到点i的前一点。从已标记的点中找到直接连接到i的点j'，作为前一点，设置：pi= j'。
（5）如果所有点已标记，则算法完全退出，否则，记k=k ∪{i}，转到（2）再继续。
1.2 Dijkstra算法的分析与待改进的地方
图1所示是上海市区的部分街道图，其中节点1为起始点。根据上一节描述的Dijkstra算法，当计算进行到若干次循环后的情况如图1所示。其中“”表示已标记的节点，“”表示与已标记节点相邻的未标记节点。可以看到，此时图1中节点1、2本身都已标记，并且它们相邻的节点也已标记。因此形如节点1、2这种类型的节点应该而且能够直接跳过算法的第（2）步，从而不做比较。设已标记节点为m个，其中相邻节点中有未标记的已标记节点有k个，我们令K={dj|j=1，...，k}，M={dj|j=1，...，m}，则KM。把集合K用平滑曲线连接起来，可以得到一个以起始点为原点的近似圆c，其中集合K中的元素位于圆c的周围长上，集合M是圆c围住的所有已标记节点。
图1 道路示意图
表1、表2是以上海市城区道路图数据为例的实验结果，从中可以观察kMax和mMax，和之间的关系。
表1的几点说明：所有数据的起点相同，终点随机选取;kMax、mMax为计算最短路径时集合K和集合M中元素曾经达到的的最大数目，和则是集合K和集合M中元素的平均个数;ArcNum为起点到终点沿最短路径所经过的弧段的个数;Distance是起点到终点的实际距离，单位是m。显然，弧段的个数与实际距离不成正比。
关于表2的几点说明：取表1的最后一组数据，即kMax=135，mMax=6 756来验证一次Dijkstra算法计算最短路径时集合K中元素个数Knum和集合M中元素个数Mnum之间的关系，Knum的采样间隔大约为10。随着计算的进行，集合K中元素的数目逐渐增多，集合M中元素的数目增长的非常快。若干次计算后，集合K、M中的元素数目分别达到最大值kMax和mMax。
观察表1、表2的数据，可以得到如下结论：
（1）随着起点和终点间距离的增大，kMax、mMax和、都增大，但kMax增长速度远小于mMax，增长速度远小于。最坏情况下与的比例只有3%左右。
（2）集合K中元素的数目始终小于集合M中元素的数目。因此，如果算法中我们只针对集合K进行操作，将极大缩小d的规模，使修改d的时间和在d中选择最小分量的时间因d的规模的缩小而降低很多。更进一步，如果d是有序的，则从k（k≤kMax）个有序数中选择一个最小数的时间复杂度为O（1），而从m（m≤mMax）个未排序数中选择一个最小数的时间复杂度为O（m）。可见，改进算法中集合K应是有序的。
Dijkstra算法中第（2）、（3）步的计算和比较结果没有保存下来，并且每次只选取d中最小的一个，所有没有选中的未标记的节点在下一次要重新计算dj并查找出一个d中最小的一个。如果把dj保存在每个节点中，并且把待比较的节点按序放到一个有序链表中，则插入/比较的时间将大大缩短。
根据图中顶点和边的个数可以求出顶点的平均出度e=m/n（m为边数，n为顶点数），这个数值代表了图的连通程度，一般在GIS网络图中，e∈[2，5]，这样如果当前永久标记的节点的出度为t，那么，下一步需扫描的点的个数就约为0～t个，时间复杂度降为O（1）。
1.3 本文提出的最短路径快速算法
1.3.1 算法描述
所有的节点分为三种状态，即未标记（US）、即将标记（TS）和已标记（AS）三种状态。每个节点都有一对标号（dj，pj），其中dj是从源点s到点j的最短路径的长度（不包括顶点到其本身）;pj则是从s到j的最短路径中j点的前一点。
（1）初始化。①创建TS队列并清空②标记起源点s为AS状态③标记起源点s的所有出边点j的状态Sj为TS，入TS队列，其中dj= lsj，TS队列按照dj的值从小到大有序排列 ④其他所有点设为US状态。
（2）取TS队列的第一个节点i（当前最小值），标记i为AS状态，并把i从TS队列中删除，若i为终点，转到（5）。
（3）判断i的所有出边点j的状态：若Sj =US，则dj=di+lij，pj=i，节点j按dj的大小入TS队列;否则若Sj=TS，并且dj>di+lij，则dj=di+lij，修改pj=i，节点j按dj的大小重新排序。
（4）若TS队列为空，转向（5），否则转到（2）继续。
（5）算法结束。若i为终点，找到最短路径;否则若TS队列为空，起点和终点不连通。
1.3.2 时间复杂度分析
由于两点之间最短路径的计算次数随两点之间经过的节点数不同而不同，使得各种输入集出现的概率难以确定，在这里我们讨论算法在最坏情况下的时间复杂度。整个算法为一重循环，循环次数为n （m最大为n）。算法的循环体部分是从第（2）到第（4）步，其中第2和4步的时间复杂度显然为O（1），关键是分析第（3）步。第（3）步中把i的的所有出边点依次有序插入TS队列，其时间复杂度取决于TS队列的规模，设TS队列的平均大小为，由以上1.2节分析可知远小于，在最坏情况下，的值大约为115，还是非常小的，因此第（3）步的时间复杂度为O（）。所以总的时间复杂度为O（（1+ +1）*n）=O（n），因此本文提出的算法的时间复杂度仅与节点数n成线性关系，与Dijkstra的时间复杂度O（n2）相比，效率提高很多。
2 改进的最短路径算法的具体实现
按照以上思路，笔者用Visual C++实现了上海黄页最短路径模块中最短路径算法。以上海市区道路为数据（共7 038个节点，9 365条弧段），计算一条贯穿全城的线路，在普通微机上约需0.1 s。
2.1 数据结构的设计
矢量地图存储的方法很多，如邻接矩阵、邻接表等。用这些常用的方法存储交通网络，存储量庞大，而且不利于网络操作。文献[6]提出的以交通节点为基础的数据结构，虽然克服了上述缺点，但是文献[6]只考虑节点以及节点之间的关系，对于弧段之间的关系没有考虑。而在实际应用中，大多数GIS网络都是有向带权图，如道路有单双向问题，从一个弧段到其相邻弧段常有转向限制等。如果我们采用转向表来表示弧段之间的转向关系，势必会造成存储容量激增，并且在计算最短路径时每一步都要查找转向表，以确定哪个弧段可以转向，造成算法很多不必要的时间开销。
为了能够清晰简单的表示弧段之间的转向关系，在节约存储空间的前提下，本文不采用转向表。在实现本文提出的算法时，我们把节点和节点之间的关系改成弧段和弧段之间的关系，使道路之间的联系更加清晰直接，从而方便计算最短路径。
我们设计了两个类来表示弧段以及弧段之间的联系，分别是类CArc和类CArcLink。类CArc包括弧段的状态sj，从起源弧段s到弧段j的最短路径长度dj （包括s和j的长度），起源弧段s到弧段j的最短路径中j的前一弧段pj，该弧段的权值（该弧段的长度或耗费的时间）;类CArcLink包括弧段之间的转向阻抗，从A弧段能否转向至B弧段的标志位（开关属性）等。
以下是类CArcLink设计的主要属性。
Class CArcLink
{int Impedance ; //转向阻抗，如耗费时间等//例如30s
bool Enabled ; //是否能够转向，如路口分时段禁行，可设置此开关变量//例如1
CNode* pNode ; //两弧段之间的节点指针//例如节点1
CArc* pNextArc ; //所连的弧段（出）指针//例如弧段11
};
在图2所示的道路图中，弧段1可以转向至弧段6、7和11，但是不可以转向至弧段12。图2的部分数据结构示意图如图3所示。
图2 道路弧段图
图3 数据结构关系图
2.2 关于本文算法实现的几点说明
关于要实现本文算法的几点说明如下：
（1）根据起始点坐标确定起始弧段。在最短路径搜索过程中，定义沿着起点到终点的方向为空间有效方向，相反的方向为空间无效方向。在实际应用中，由于受客观因素的限制，可能需要在无效方向上的一定距离内搜索，因此一般情况下，如果起始路径是双向的，则起始弧段有两条，设为S1和S2，一并初始化。
（2）本文从减少计算最短路径时的路径转向判断以及降低内存耗费考虑，取消转向表，单独设置一个时态参数表，根据实测的交通量可将一天24小时划分为若干离散时段，各时段不一定等长，以及划分的时段密度也可以不一致，利用定时器根据预先定义的时段来设置类CArc和类CArcLink的与时态有关的属性，实现静态触发修改（经验值修改）。也可以根据实测值或者人工智能推理预测值动态实时触发修改。
（3）查找最短路径和查找最小时间耗费的问题在理论上是等价的。查找最小时间耗费，除了要加上弧段的权值（该路段上耗费的时间），还要加上弧段之间的转向阻抗（转向耗费时间），即在改进算法的第（3）步，把dj=di+lij修改为dj=di+lij+Iij，其中Iij是从弧段i到弧段j的转向阻抗。
3 结 语
本文在分析总结Dijkstra算法的基础上，对此算法进行了改进，提出了一个新的最短路径快速实现算法，使时间复杂度由O（n2）降低到O（n）。在算法的实现上，提出了一种区别于传统方法的弧段―弧段存储结构，使路径之间的关系更加清晰直接;把路径与时态有关的属性信息分开存储，并通过触发器来修改属性，提高了算法的实现效率，减小了执行算法所需的运行空间。本文提出的快速实现算法已成功的应用于上海黄页基于掌上电脑的电子地图的最短路径实现中，取得了令人满意的效果。
参考文献
[1] R.K.Ahuja，K.Mehhorn，J.B.Orlin. Faster Algorithms for the Shorest Path Problem. Technical Report[J]. CS-TR-154―88，Department of Computer Science，Princeton University，1988.
[2] D.P.Bertsekas. The Auction Algorithm for Shortest Path SIAM J[J].Opt.， 1991（1）：425-447.
[3] A.V.Goldberg. Scaling Algorithms for the Shortest Paths Problem[J]. In Proc. 4nd ACM-SIAM Symposium on Discrete Algorithms，Pages 1993：222-231.
[4]乐阳. Dijkstra最短路径算法的一种高效率实现[J]. 武汉测绘科技大学学报，1999，24（3）：209-211.
[5] 韩俊卿.基于GIS的城市道路网最短路径算法探讨[J]. 科技传播， 2010（8）： 110-111.
[6] 徐业昌， 李树祥， 朱建民，等. 基于地理信息系统的最短路径搜索算法[J]. 中国图象图形学报，1998（1）： 43-47.
[7] 陆锋， 卢冬梅， 崔伟宏. 交通网络限制搜索区域时间最短路径算法[J]. 中国图象图形学报， 1999（10）：47-51.
[8] 陈述彭. 城市化与城市地理信息系统[M].北京：科学出版社，1999.