障碍物存在的最短路径算法及其在车载导航中的应用

引言

路径选择问题是解决车载导航系统中的核心问题，归根结底是最短路径问题。现有的最短路径算法有很多，如迪杰斯特拉（Dijkstra）、弗洛伊德（Floyd）及其改进算法、盲目捜索法，启发式A*算法、人工神经网络、遗传算法、蚁群算法等［%而这其中又是以迪杰斯特拉及其改进算法最经典,是研究得最多的一种算法，并取得了一定的成果，然而，对这些成果进行分析发现，研究的这些算法都是静态的，以图论为基础的方法，并没有考虑到障碍物的影响。因此，本文主要对有障碍物影响的情况下的最短路径算法进行研究，并利用MapX控件实现了最短路径的算法，在车载导航中取得了较好的应用。

1Dikjsrta算法存在的问题

Dikjsrta算法是由荷兰数学家E.W.Dikjsrta于1959年提出单源最短路算法，是目前求解最短路问题的理论上最完备、应用最广的经典算法，它可完成从指定图中所有其他节点的最短路径，它是主要路径长度递增产生最短路径算法，此算法在诸多教材中均有阐述。从所介绍的算法不难看出存在两点不足:①只考虑静态的最短路径，没有及时反映出存在障碍物（如交通阻塞、修路等情况）下的最短路径；②图的存储结构中存在着大量的8,浪费了大量的存储空间。因此本文从以上两个方面加以改进。

2Dikjsrta算法的改进

2.1有障碍物存在时的改进Dikjsrta算法

通过对各类公交流量的分析和研究，可将城市道路障碍物分为阻塞和繁忙两种状态，如修路行不通为阻塞状态、上下班堵车为繁忙状态，在这两种状态情况下，必须另录一条最短路径以获得时间最短。将障碍物反映到图上，则存在两种情况：一是正好在相应节点上（如图1节点2上），贝屿其相连的节点上各边权值变为8；二是在相应的某一条边上（如节点1-3）之间，贝惧相邻接的邻接矩阵变为8。其改进算法如下：

建立邻接矩阵A[v,][vJ]„若v障碍物正好处于图的节点，则此节点是车载不允许经过的节点，A[:][Vj]=8,亦矩阵中V所在的列的元素均取8。若障碍物正好位于两节点之前,即此段路程不通必须加以回避，设e,j=(v„Vj)为必须回避的边,则A[v；][vj]=8。

初始化。S={vs)(vseV),dist[vi]=A[vs][vi],path[Vj]={vs},vieV,i=1,2,…，n。

选择Vk，使得dist[Vk]=min(dist[v』VieV-S),S=SU{Vk}。Vk为目前求得的下一条从Vs出发的最短路径的终点。如果Vk夭Vt，转向(4),否则结束,dist[Vt]即为回避的点、边、路径障碍下从Vs到顶点vt的最短路径。

修改从v出发到集合V-S任一顶点Vi的最短路径长度。设V为路径path[Vk]倒数第二个节点。若dist[Vk]+A[Vk][Vi]<dist[Vi],则dist[i]=dist[Vk]+A[Vk][Vi],path[Vi]=path[Vk]U{财，转向(3)。

图1所示是一种有路障的加权图G',图1中，假设节点2号有路障，另外1-3号节点的路段正在修路不能通行，其存储的邻接矩阵如图2所示。

图2图G'的邻接矩阵

2.2存储结构的改进

无论是有无障碍物的Dikjsrta算法，采用矩阵来存储点与点间的拓扑关系，行数和列数相同，矩阵中i行J列的值对应着点i和点J之间的权值，起点和终点为同一点时权值用0表示，两点之间没有直接通路时权值用8表示。矩阵中含有大量的0和8,增加了无效循环次数，在存储上也占用了大量的空间，浪费了大量的空间。为提高内存的利用率，本文采用的邻接表存储如图3所示。

用链表数组MGrpah表示存储矩阵G时，可将其每一行用一个单链表来表示，链表中只有非8元素，每个节点有两个元素，一个为所在的列值，一为点的权值。其伪代码如下:

Typedfstruct

{Intr,v；

Mnode*next；

}Mnode；

ClassMGraph{

Public:

Mnode*first,*current；

Mgraph(){current=null；first=current；}

Voidsetfirst(Mnode*p){first=p；current=first；}

Mnode*GotoFirst(){if(first){current=first；returncurrent；}

Elsereturnnull；}

VoidAdd(Mnode*p){current->next=p；current=p；}

Mnode*Next(){if(current->next){current=current->next；returncurrent；}

ElsereturnNULL；}

}

然后可用一维数组D来存储各顶点到源点的最短距离,并用一维数组P来存储前驱点，再用一个辅助双向链表来存储正在参与比较的节点(使用双向链表的目的是在删除节点时降低时间复杂度)。其代码如下：

Typedefstruct{intr；Node*next,*prev；}chinaNode；

Classpath{

public:

chainNode*first,*current；

intn；

path(){n=0；current=null；first=null；}

voidsetfirst(chainnode*p){first=p；current=first；n=1；}

voidAddTail(chainNode*p){current->next=p；p->prev=current；current=p；n++}

intdelete(chainNode*p)；

chainNode*Next(){if(current->next){current=current->next；

returncurrent；}elsereturnnull；}

boolIsEmpty(){returnn==0；}

}

2.3改进算法的实现步骤

改进算法的实现步骤如下：

将与V。直接相连的节点的D[vJ初始化为其权值,其余的置为机器所允许的最大值。

将与V。直接相连的顶点加入到链表Path中。

在Path中找到权值最小的节点w,并在Path中删除此顶点，如果剩余节点数为。则结束。

修改最短路径：在G里与w直接相连的其余各节点Vj的权值中比较D[Vj]与D[w]+s(w,vD的大小，如果D[vJ小于D[w]+s(w,Vj),并且如果D[Vj]为8,则将Vj加入到Path中，然后将P[vJ的前驱设置为w,并修改最短路径D[vJ=D[w]+s(w,V)。重复步骤(4)。

根据以上思路，利用MapX控件，结合可视化编程语言,对武汉市地图矢量化，去除多余的结点，构建拓扑关系，结合改进的算法，进行编程，其实现的界面如图4所示。

3结语

本文在研究现有的Dikjsrta算法的基础上，讨论了有障碍物存在的Dikjsrta的算法，并对其存储结构进行了一点小的改进，给出了具体的实现过程，提高了存储效率。存在的不足是没有对时间与空间复杂度进行量化，另外，对其搜索方法

也没有加以改进，这将是下一步努力改进的方向。

图4障碍特存在的最短路径展示图

20211116_6193be3cc09ae__障碍物存在的最短路径算法及其在车载导航中的应用