基于可视图法的改进Dijkstra算法

基于可视图法的改进Dijkstra算法（共4篇）

基于可视图法的改进Dijkstra算法 篇1

基于可视图法的改进Dijkstra算法

针对基于可视图的.Dijkstra单向最短路径规划算法难以加入飞行性能约束的问题,将飞行轨迹视为一系列直线和圆弧,利用转弯离开点与进入点构建三圆弧组合实现避障转弯,成功地在算法中引入最小转弯半径约束.采用纯数学公式推导,详细介绍了推导过程.算法减少了无关节点运算,提高了查询与规划最短路径效率.通过对比仿真,验证了算法有效性.

作 者：李大东 孙秀霞 彭建亮 孙彪 LI Dadong SUN Xiuxia PENG Jianliang SUN Biao  作者单位：空军工程大学工程学院,西安,710038 刊 名：电光与控制  ISTIC PKU英文刊名：ELECTRONICS OPTICS & CONTROL 年，卷(期)： 17(3) 分类号：V249 关键词：航迹规划   Dijkstra算法   可视图   避障路径规划  

基于可视图法的改进Dijkstra算法 篇2

在现如今的物流工程中存在许多问题都可以用一个网络来描述, 例如, 运输问题[1]、混流装配线问题[2]以及计算机网络问题[3]等。对于最短路问题、最小费用问题、最大流问题等都是网络优化问题, 除了利用比较熟悉的动态规划[4]技术外, 现在的一些比较新的进化算法在这方面也展现出了它们的优越性, 例如, 遗传算法[5], 蚁群算法[6]等。但在求最短路问题中, Dijkstra算法算是一种相对比较经典的算法, 在文献[7]中, 刘建美根据现在交通网络的需求, 结合实际中根据时间变化交通网络中的拥堵情况, 对Dijkstra算法进行改进, 用于求解动态网络中的最短路问题, 在文献[8]中, 鲍培明为降低迭代的次数, 减少寻求最短路的时间, 对Dijkstra算法进行改进, 利用逼近的原则, 求解最短路。对于给定的一个网络图, 在寻求最短路时, 可能两个点相对较近, 如对所有节点都进行迭代计算, 将做无用功。并且在原有的Dijkstra算法中, 在求出最短路时, 需要返还寻找最短路中经过的路径, 且有多条相同最短路径时, 只是选择其中一条输出, 为提高Dijkstra算法再求最短路问题的效率, 本文对Dijkstra算法进行了改进, 使其在求最短路时, 一旦经过终点, 即结束迭代, 输出最短距离, 并且在迭代过程中, 将到达每个节点的最短路径保存在一个变量中, 在到达终点时, 即可直接输出最短路径, 如有多条路径, 会同时输出。

1 Dijkstra算法简介

1.1 图和赋权图

在网络图中, 设图G是指一个有序三元组 (V, E, 准) , 其中V表示非空顶点集合, E表示边集, 而准表示关联函数, 它使G的每条边对应于G的无序顶点对。例如:

对G的每一条边e, 可以赋以一个实数t (e) , 称为e的权, G连同它边上的权称为赋权图。权的含义比较广泛, 在本文中, 主要是求最短路, 以时间为主要变量, 所以在本文中, 权表示时间。在网络图G中, 给其边赋以一定值t (e) , 表示网络图中两点之间的时间距离, 运用Dijkstra算法求其中任意两点之间的最短路径。

1.2 Dijkstra算法

Dijkstra算法是由荷兰计算机科学家狄克斯特拉于1959年提出的, 因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法, 解决的是有向图中最短路径问题。Dijkstra算法主要特点是以起始点为中心逐渐向目标顶点扩展, 直到扩展到终点为止。

Dijkstra算法的具体步骤如下所示:

用P, T分别表示某个点的P标号和T标号, Si表示第i步时, 具P标号点的集合。为了在求出从vs到各点的距离的同时, 也求出从vs到各点的最短路, 给每个点v以一个λ值, 算法终止时, 如果λ (v) =m, 表示从vs到v的最短路上, v的前一个点是vm;如果λ (v) =M, 则表示G中不含有从vs到v的路;λ (v) =0, 表示v=vs。

给定赋权有向图G= (V, E) ;

开始 (i=0) 令S0={vs}, P (vs) =0;λ (vs) =0, 对每一个v≠vs, 令T (v) =+∞, λ (v) =M, 令k=s。

(1) 如果Si=V, 算法终止, 这时, 对每个v∈Si, d (vs, v) =P (v) ;否则转入 (2) 。

(2) 考查每个使 (vk, vj) ∈E且vj埸Si的点vj。

如果T (vj) >P (vk) +tkj, 则把T (vj) 修改为P (vk) +tkj, 把λ (vj) 修改为k;否则转入 (3) 。

如果T (vji) <+∞, 则把vji的T标号变为P的标号P (vji) =T (vji) , 令Si+1=Si∪{vji}, k=ji, 把i换成i+1, 转入 (1) ;否则终止, 这时对每个v∈Si, d (vs, v) =P (v) , 而对每个v埸Si, d (vs, v) =T (v) 。

2 改进Dijkstra算法的最短路算法

2.1 Dijkstra算法分析

根据以上对Dijkstra算法的介绍, 对于所有路段都是双向问题中, 在求解最短路时, 对于相连较近的两个节点之间求最短路, 将会对所有节点进行计算, 计算量较大。并且在求出最短路时, 不能够直接输出最短路的路径情况, 需重新对计算过程进行分析, 根据计算过程, 找出最短路径。

2.2 建立最短路数学模型

在程序设置中, 语言选择的是C语言, 主要运用二维数组的形式输入数据, 所以在对网络图中的节点标注是从0开始, 0表示起点, n表示终点;节点数根据网络图中的具体情况而定。变量设置如下所示:

i, j表示节点 (i, j=0、1、2、3……) ;xij表示节点i, j之间的通行情况, xij=1表示从节点i, j之间通过, xij=0表示不从节点i, j之间通过;M表示一个大数;tij表示从节点i到节点j运行时间;T表示从起点到终点的运行时间。

目标函数:

约束条件:

2.3 改进Dijkstra算法

假设共有m个节点, B={0、1、2……m-1}, 每次迭代到达各个顶点的最短距离存入sum[][]中, 达到每个节点的最短路径存入w[][][]中, 改进Dijkstra算法后的具体步骤如下所示, 流程图见图1。

Step 1开始 (k=0, j=0) , 令s[m][m]={0}, w[m][m][m]={0}, sum[m][m]={0}, min=0, x[m][m]={0}, 根据以上所标节点, 结合两个节点之间运行的时间输入矩阵t[m][m], 如若i, j两个节点之间无直接相连的路段, 则t[i][j]=M, 根据下面计算要求, 令t[i][i]=M, 转入Step 2;

Step 2确定起始点和终点, 输入起点l1, 终点l2, 转入Step 3;

Step 3运用所给时间矩阵t[m][m], 求出l1点到各点的距离sum[l1][i]修改为min+t[l1][i], 对应经过路段w[i][][i]为0*100+i, 因为从0点出发, 所以在求最短路的过程中, 不再回到0点, 所以变化起始矩阵, 对于所有到达0的所以路段都赋予一个大数, 即t[i][0]=M (i∈B) , 令min=min{sum[0][i]} (i∈B) , 对于存入min的i赋值给k, 将w[k][][]中的存入s[][]中, j+1赋给j, 转入Step 4;

Step 4如果k=l2, 转入Step 8;否则转入Step 5;

Step 5运用所得矩阵, 求出0到各点的距离sum[k][i]修改为min+t[k][i], (i∈B) , 为便于一下比较计算, 将M赋给sum[j-1][k], 为求最短路, 所以不会出现回头路, 所以对于所有到达k的路段赋以大数M, 即t[i][k]=M, (i∈B) , 转入Step 6;

Step 4如果k=l2, 转入Step 8;否则转入Step 5;

Step 5运用所得矩阵, 求出0到各点的距离sum[k][i]修改为min+t[k][i], (i∈B) , 为便于一下比较计算, 将M赋给sum[j-1][k], 为求最短路, 所以不会出现回头路, 所以对于所有到达k的路段赋以大数M, 即t[i][k]=M, (i∈B) , 转入Step 6;

Step 6判定sum[j-1][i]和sum[j][i]的大小, (i∈B) , 若前者小, 则将前者的值赋给后者, 转入Step 7;若后者小, 将原有w[i][][]中的数据清空, 并且将s[][]中的数据输入w[i][][]中, 再将100*k+i接在替换w[i][][]中第一个为0的数, 转入Step 7;如若两者相等, 则将两个相等的路径都存入w[i][][]中, 转入Step 7;

Step 7 min=min{sum[k][i]} (i∈B) , 将对应输入min中的i赋值给k, 将s[]清空, 将w[k][][]中的值赋给s[][], j+1赋值给j, 转入Step 4;

Step 8对于s[i][]中的所有非0值, s[i][]除以100剩下的整数赋给c, 余数部分赋给d, x[c][d]=1, 输出所有x[][], 为路径的选择情况, 最短距离为min, 算法终止。

3 最短路算法的应用举例

在自动化仓库物流系统中, 需要将装有货物的容器通过自动化输送设备从仓库的位置0移动到位置7, 共有8个节点, 网络图如图2所示, 各个节点之间的通行时间见表1。为使得输送时间最短, 寻求最短路径, 结合改进后的Dijkstra算法, 运用C语言进行编程, 运行结果如图3所示。

由运行结果可以看出有两个输出结果, 第一个为x[0][1], x[1][4], x[4][7]等于1, 表示路径为0-1-4-7, 第二条为x[0][3], x[3][6], x[6][7]等于1, 表示路径为0-3-6-7, 最短时间为9。

4 总结

根据最短路问题, 建立数学模型, 利用Dijkstra算法来求最短路问题, 将Dijkstra算法中起始输入的邻接矩阵与矩阵的基本变换相结合, 实现了求网络图中任意两点之间最短路的问题, 只要网络图给定, 输入起始点和终点, 就可以直接求出最短路径以及最短距离, 如在迭代过程中, 存入min中的点为终点, 则终止迭代, 避免了对全部顶点的迭代, 节约了时间。但是在求解过程中, 是以二维数组的形式输入时间的邻接矩阵, 在计算过程中, 占用空间较大, 仍需对其进行完善。

摘要：Dijkstra算法是求解最短路径问题的经典算法。在现如今的城市交通网络中, 经常需要寻求两个地点之间的最短距离, 减少运输时间。本文将Dijkstra算法与C语言相结合, 对Dijkstra算法进行改进, 根据实际网络图的情况, 建立了相应的数学模型, 运用C语言编程, 在给定的网络图中, 实现了只需确定起始点和终点, 就可以直接输出最短路径和最短距离的功能。在有多个相同最短路径的情况下, 会将多个最短路径一起输出, 在搜索到终点时, 立即跳出, 结束循环。在一般情况下, 无需对所有点进行迭代, 提高了效率。这种方法可以应用到现在的物流运输中, 以此来节约时间, 降低成本。

关键词：物流工程,改进Dijkstra算法,数学模型,最短路问题,C语言

参考文献

[1]郑龙, 周经伦, 易凡, 等.大规模随机运输网络的路径优化[J].系统工程理论与实践, 2009, 29 (10) :85-93.

[2]苑明海, 李东波, 于敏建, 等.面向大规模定制的混流装配线平衡研究[J].计算机集成制造系统, 2008, 14 (1) :79-83, 131.

[3]Azaron, A.Bicriteria shortest path in networks of queues[J].Applied Mathematics and Computation, 2006, 182 (1) :434-442.

[4]李端, 钱富才, 李力, 等.动态规划问题研究[J].系统工程理论与实践, 2007, 27 (8) :56-64.

[5]郎茂祥, 胡思继.用混合遗传算法求解物流配送路径优化问题的研究[J].中国管理科学, 2002, 05:52-57.

[6]张维泽, 林剑波, 吴洪森, 童若锋, 董金祥.基于改进蚁群算法的物流配送路径优化[J].浙江大学学报 (工学版) , 2008, 04:574-578, 597.

[7]刘建美, 马寿峰, 马帅奇, 等.基于改进的Dijkstra算法的动态最短路计算方法[J].系统工程理论与实践, 2011, 31 (6) :1153-1157.

基于可视图法的改进Dijkstra算法 篇3

关键词：Dijkstra算法 K最短路径 公共交通 衔接规划

Solves K most shortpath improvement Dijkstra algorithm

Zhang SongWang JunMa Jinping

Abstract:This article first from the orbital transportation and the conventional transportation engagement plan angle of view,elaborated solves the K most shortpath question to optimize in the public transportation wire the significance.Then most shortcircuits in Dijkstra in the algorithm foundation,creatively has introduced many P sign and many T sign records the beginning to this node K shortpath and the upper boundary,after makes the improvement the algorithm success to solve the K most shortpath.Finally uses the C language to carry on the realization to the algorithm,and had the test data to carry on the algorithm test stochastically,the test result has indicated this algorithm counting yield and the application prospect.

Keywords:Dijkstra algorithmK most shortpath Mass transit Engagement plan

【中图分类号】F542【文献标识码】C 【文章编号】1009-9646(2009)04-0029-03

1．引言

最短路径问题是网络分析中最基本的组合优化问题之一，在公交线网规划中的应用十分广泛。尤其是随着我国经济的飞速发展和城市化进程的加快，城市轨道交通已进入大发展时期。作为城市客运交通骨干，轨道交通应该与常规公交、铁路客运、公路客运、航空客运、小汽车、自行车和步行等多种交通方式密切配合，这就对城市交通的发展提出了衔接规划的要求。轨道交通的衔接规划是基于轨道交通的发展,对其沿线的交通资源配置优化和整合,达到客运交通资源最优化。其中很重要的任务就是对现有城市公交线网进行重新规划。然而在实际进行公交线网优化设计中，最短路径模型往往无法直接应用。原因主要有两个方面：首先，在线网规划中往往要求公交路线必需经过某些指定路段（地铁终点站、主要接驳站等），或者必需不经过某些指定路段（与地铁线路重复的路段、需要抽疏的路段等），从而出现了指定路线的最短路径问题。其次，在线网规划中有很多无法通过数学模型具体表达的要求，决策者往往需要多个线路设计方案，并从中进行决策，从而出现了K最短路径问题。

在非负权网络最短路径问题中，最有效的方法是Dijkstra算法［1］ 。基于这个算法，还出现了一些对Dijkstra算法的扩展和改进［2］，其中具有代表性的是TQQ、DKA、DKD ［3］、HOPA ［4］、A*算法［5］等。对于K最短路径问题，Yen提出了递推算法［6］，基于动态规划，李成江提出了复杂度为0(m+nlgn+mlgk)的算法［7］。由于Dijkstra算法的高效性和易扩展性，本文在经典的Dijkstra算法的基础上，提出了新的求解K最短路径的算法。

2.求解K最短路径的改进Dijkstra算法

对于一个具有n个节点和m条边的非负权有向网络G(V,E,L)，Dijkstra算法求解起点vs到vt的最短路径的基本思想是：如果节点序列{vs,…,vi,vt}是从vs到vt的最短路径，则{vs,…,vi}必为从vs到vi的最短路径，即从起点到某节点的最短路权一定是它全部紧前节点的最短路权与相应路权之和的最小值。在Dijkstra算法中，对每个节点进行标号，或者是试探性T标号，或者永久性P标号。T(vi)标号表示从vs到vi的最短路权的上界，是一种临时标号。P(vi)标号表示从vs到vi的最短路权，该标号一旦确定不再改变。算法的过程是不断修正节点的T标号值，将最小T标号修改为该节点的P标号，直至得到vt的P标号。

在K最短路径问题中，我们注意到从起点vs到节点vi的第k短路权，k=1,…K，一定是vs到vi的全部紧前节点的前k短路权与相应路权之和的第k小值。因此，计算节点vi的第k短路径时只需考虑vi的全部紧前节点的前k短路径。为了记录前K短路径，我们需要为每个节点设置K个标号，或者是试探性T标号，或者永久性P标号。Tk(vi)表示起点vs到vi的第k短路径路权的上界；Pk(vi)表示起点vs到vi的k最短路权值，而且一定有T1(vi)≤T2(vi)≤…≤TK(vi)，P1(vi)≤P2(vi)≤…≤PK(vi)。 在算法中，我们需要不断修正节点的K个T标号，将其中最小的T标号修改为该节点相应的P标号，直到得到PK(vi)为止。具体步骤如下：

步骤0.给vs以P标号，P1(vs)=0；

其余各点均给T标号，Tk(vi)=+∞,vi∈V/{vs},k=1,…,K。

步骤1.vi为刚得到Pk(vi)标号的节点，考虑节点vj:(vi,vj)∈E。

(1)如果Pk(vi)+lij＜Tk(vj)，确定一个q值，满足

Tq-1(vj)≤pk(vi)+lij＜Tq(vj)

(2)将Pk(vi)+lij按照q值插入vj的K个T标中，即

Tk(vj)Tk-1(vj),Tk-1(vj)Tk-2(vj),…,Tq+1(vj)Tq(vj),Tq(vj)Pt(vj)+lij

步骤2.比较所有T标号的值，将最小的T标号改为相应的P标号，即

Pk*（vj*）Tk*(vj*)=mink,j{Tk(vj)}，记录(vi,vj*)。

如果存在多个最小者时，将它们同时改为P标号；

如果Pk(vt)已经标出，算法结束；否则，返回步骤1。

3.算例求解

下面我们用一个算例来说明新算法的步骤。求解网络（如图1所示）中从v0到v4的前3短路径。

步骤0，P1(v0)=0,Tk(vi)=+∞,i=1,…,4,k=1,2,3。

迭代一.（v0）：

步骤1，考虑节点v1、v2，计算其T标号值：

P1(v0)+l01=0+2＜T3(v1)=+∞，得到q=1，T3(v1)=T2(v1)=+∞，

T2(v1)=T1(v1)=+∞，T1(v1)=P1(v0)+l01=2；

p1(v0)+l02=0+3＜T3(v2)=+∞，得到q=1，T3(v2)=T2(v2)=+∞，

T2(v2)=T1(v2)=+∞，T1(v2)=P1(v0)+l02=3。

步骤2，比较所有标号，T1(v1)=2是最小的T标号，将其改为P1(v1)=2，记录(v0，v1)。

迭代二.（v1）：

步骤1,考虑v2、v3、v4，计算其T标号值：

P1(v1)+l12=2+2＜T3(v2)=+∞，得到q=2，T3(v2)=T2(v2)=+∞，

T2(v2)=P1(v1)+l12=4；

P1(v1)+l13=2+5＜T3(v3)=+∞，得到q=1，T3(v3)=T2(v3)=+∞，

T2(v3)=T1(v3)=+∞,T1(v3)=P1(v1)+l13=7；

P1(v1)+l14=2+1＜T3(v4)=+∞，得到q=1，T3(v4)=T2(v4)=+∞，

T2(v4)=T1(v4)=+∞,T1(v4)=P1(v1)+l14=3；

步骤2，比较所有的T标号，T1(v2)=T1(v4)=3最小，P1(v2)=3，记录(v0,v2)，

P1(v4)=3，记录(v1,v4)。

迭代三.（v2）：由于v4没有紧后节点，故不考虑。

步骤1，考虑节点v1、v3、v4，计算其T标号值：

P1(v2)+l21=3+2＜T3(v1)=+∞，得到q=2，T3(v1)=T2(v1)=+∞，

T2(v1)=P1(v2)+l21=5；

P1(v2)+l23=3+3＜T3(v3)=+∞，得到q=1，T3(v3)=T2(v3)=+∞，

T2(v3)=T1(v3)=7,T1(v3)=P1(v2)+l23=6；

P1(v2)+l24=3+4＜T3(v4)=+∞，得到q=2，T3(v4)=T2(v4)=+∞，

T2(v4)=P1(v2)+l24=7；

步骤2，比较所有T标号，T2（v2）=4最小，P2(v2)=4，记录(v1,v2)。

继续迭代，直至得到P3(v4)=7，并得到从v0到v4的前三短路为分别为v0→v1→v4，v0→v2→v1→v4和v0→v2→v4，它们的路权分别为3，6和7。

迭代过程如图2所示。

4.算法测试

本算法用C语言实现，并对算法进行了测试。测试环境为：Microsoft Windows XP Service Pack 4；Inter(R) Core(TM)2Duo CPU 1.5GHz；Phys Memory：1023MB DDR2-667MHz。用伪随机数随机生成网络邻接矩阵，产生不同规模的问题，n=20,40,60,80,100，每种规模生成10个问题，分别计算前2，3，4短路径，统计计算所需的CPU时间（单位秒），结果如表1所示。

当前节点考虑节点标号最小标号修改后标号

初始值

v0p1=0

v1T1=∞,T2=∞,T3=∞

v2T1=∞,T2=∞,T3=∞

v3T1=∞,T2=∞,T3=∞

v4T1=∞,T2=∞,T3=∞

迭代一v0

v1T1=2,T2=∞,T3=∞T1=2P1=2,T2=∞,T3=∞

v2T1=3,T2=∞,T3=∞

迭代二v1

v2T1=3,T2=4,T3=∞T1=3P1=3,T2=4,T3=∞

v3T1=7,T2=∞,T3=∞

v4T1=3,T2=∞,T3=∞T1=3P1=3,T2=∞,T3=∞

迭代三v2

v1P1=2,T2=5,T3=∞

v3T1=6,T2=7,T3=∞

v4P1=3,T2=7,T3=∞

*v2P1=3,T2=4,T3=∞T2=4P1=3,P2=4,T3=∞

v4不指向任何节点

迭代四v2

v1P1=2,T2=5,T3=6T2=5P1=2,P2=5,T3=6

v3T1=6,T2=7,T3=7

v4P1=3,T2=7,T3=8

迭代五v1

v2P1=3,P2=4,T3=7

v3T1=6,T2=7,T3=7T1=6P1=6,T2=7,T3=7

v4P1=3,T2=6,T3=7T2=6P1=3,P2=6,T3=7

*v1P1=2,P2=5,T3=6T3=6P1=2,P2=5,T3=6

迭代六v1

v2P1=3,P2=4,T3=7

v3P1=3,T2=7,T3=7T3=7P1=3,P2=7,P3=7

v4P1=3,P2=6,T3=7

v3

v2P1=3,P2=4,T3=7T2=T3=7P1=3,P2=4,P3=7

v4P1=3,P2=6,T3=7T3=7P1=3,P2=6,P3=7

v4不指向任何节点

图2



表1 算法计算统计结果

n平均时间(s)最短时间(s)最长时间(s)

K=2

202.32.32.4

404.94.75.2

608.17.49.2

8010.09.710.4

10012.412.012.8

K=3

203.43.33.4

407.77.58.1

6011.511.812.1

8015.315.015.8

100内存溢出

K=4

204.64.54.7

4010.19.610.7

6015.415.015.9

80内存溢出

100内存溢出

从统计结果可知，本算法求解100个节点的网络前2短路径平均需要CPU时间12.4秒。在测试环境内存的限制下，求解前3短路径时最多可以计算80个节点的网络，而求解前4短路径时最多可以计算60个节点的网络。

根据以上计算结果，可以相信在计算机内存可以保证的条件下，能够计算200个节点的网络前5最短路径问题，满足城市公交线网优化的要求。

参考文献

［1］ Dijkstra E.W.A note on two problems in connexion with graphs ［J］.Numerische Mathematik,1959,1:269~271

［2］ Xu M.H.，Liu Y.Q.，Huang Q.L.,Zhang Y.X.,Luan G.F.An improved Dijkstra s shortest path algorithm for sparse network ［J］.Applied Mathematics and Computation,2007,185:247~254

［3］ Zhan F B.Three fastest shortest path algorithms on real road networks ［J］.Journal of Geographic Information and Decision Analysis,1997,1(1):69~82

［4］ 王景存、张晓彤、陈彬、陈和平.一种基于 Dijkstra算法的启发式最优路径搜索算法［J］.北京科技大学学报,2007，3（3）：346~350

［5］ Rothkopf H,Stark R M.Competitive bidding:A comprehensive bibliography［J］.Operations Research,1979,27(2):365~390

［6］ Yen J.Y.Finding the k shortest loopless pathes in a network ［J］,Management Science,1971,17:712~716

基于可视图法的改进Dijkstra算法 篇4

关键词：停车场,泊位诱导,最短路径,Dijkstra,VC

目前停车诱导系统研究主要是针对停车场外的停车诱导, 对停车场内的诱导重视不足。其中停车场内的诱导功能, 有的是通过管理人员对车位占用地图视觉判断, 有的是根据预设的引导管理原则程序处理排队引导车位序列, 停车效率低, 智能化程度不高。针对现代大型停车场管理系统中存在的这一问题, 本文欲从另一个角度研究用户停车线路, 根据用户所选车位, 将之转化为最短路径问题, 并引用Dijkstra改进算法对其进行求解, 最后结合实例给出仿真结果, 进而把最短路径示意图呈现给用户。

1应用分析

1.1停车场结构分析

图1为某停车场的部分车位示意图, 停车场内的车位网络可以化成无向带权图, 两者的概念对应如下[1,2]:

节点:道路的交叉口、停车位或停车场出入口。

边:两节点之间的路段称之为边。

边的权:是路段某个或某些特征属性的量化表示。根据不同的优化目标, 可以选择不同的路段属性, 如路段长度、路段平均行程时间等作为该路段对应的边的权, 或称为道路权重。

将车位、交叉口或停车场的出入口与图1中加粗线段 (行车线路) 的交点相对应, 在规定了节点、边及其权值之后, 便将车位和停车线路抽象为一个无向带权图2, 其中Pi表示车位i, Cj表示交叉口j。

由于车位对称, 可能存在两个或多个车位对应于同一点, 如图2中P7、P26、P28、P30和P33都代表了两个车位。从而将本文要解决的问题转化为从入口节点到某一停车位的最短路问题。道路权重的标定决定了最短路径搜索的依据, 也就是搜索指标, 常用的路权指标有停车距离或停车时间。

1.2数据的存储

图2中的每一个点可以通过测量停车位的地理信息即经度、纬度来确定, 而边是由两点和人工测得的权值确定。为了方便查找最短路径, 文中设计了如下数据结构来存储节点和边信息。利用Microsoft Access创建数据库并创建两个表:点信息表1和边信息表2。

2Dijkstra算法的改进与实现

2.1Dijkstra传统最短路径算法[1]

Dijkstra算法用于计算一个源节点到其他节点的最短代价路径, 有较高的应用价值。1996年Zhan和Noon使用实际交通网络测试了17种算法中的15种, 测试结果表明计算一点到其他点的最短路径最快的算法是Dijkstra算法。其基本思想:

设从节点S出发, 查找从它到其他各节点的最短路径。把图中的所有节点分为两组, 第一组包括已经确定最短路径的节点, 第二组包括尚未确定最短路径的节点, 按最短路径长度递增的顺序逐个把第二组的节点加到第一组中, 直到从S出发可以到达的所有节点都包括在第一组中。在此过程中, 总保持从S到第一组的各节点的最短路径长度都不大于从S到第二组的任何节点的最短路径长度。另外, 每一个节点对应一个距离值, 第一组的节点对应的距离值就是从S到到此节点的只包括第一组的节点为中间节点的最短路径长度。

2.2Dijkstra算法的改进[3]

传统的Dijkstra最短路径算法是计算某一确定起点到其它任一节点的最短路径, 显然计算量比较大。我们只关心从一确定起点到另一确定终点的最短路径, 没必要计算所有节点。传统Dijkstra算法计算时是按从起始节点到其余节点的最短路径权值由小到大的逐个加入最短路树中, 而且加入了最短路树中的每一个节点的最短路径都已求出, 所以Dijkstra改进算法的基本思想可以如下:

以起始点 (假设为S) 为树根, 按照距S的最短距离以及节点的相邻关系, 逐次放入树中, 由近至远, 直到目标点放入树中, 形成最短路树, 树上每一个节点与S的路径都是最短路径。其节点标记与传统Dijkstra算法完全相同, 算法步骤的方法、原理也相同, 只是算法的停止条件是目标点是否进入最短路树, 而不是把所有节点是否标记作为运算停止的判断条件, 因此计算量大大减少。

2.3Dijkstra改进算法的实现

(1) 初始化。起始点S的P标号为0, T标号为∞, 其余点的P标号为∞, T标号为0;

(2) 设目标点为X, 判断X的P标号是否为∞, 若是转步骤 (3) , 否则算法结束;

(3) 令Z=S, 即把起始点S的标识符赋值给变量Z;

(4) 若Z与X相同, 算法结束, 否则转步骤 (5) ;

(5) 若与Z相邻的点的T标号大于Z的P值与Z到该点的路径权值之和, 将该点的T值修改为Z的P值与Z到该点的路径权值之和;

(6) 从所有非0和∞的T值中找出最小的, 并将其赋给该点的P值, 同时将该点的T值修改为0, 该点的标识符V赋给Z, 转步骤 (4) 。

3实例仿真

根据上述算法, 用VC开发了一个查询最短路径的仿真系统[4]。

3.1系统特点

(1) 动态录入点和边信息的功能。用户只需输入测得点的经度、纬度, 系统在画图时自动将其转化成为标准坐标系统下的横坐标和纵坐标。

(2) 画图功能。点击画图菜单, 系统根据用户输入的点和边信息可生成如图3所示的车位和停车线路示意图。

(3) 查询并显示最短路径功能。系统可根据需求设置任意点为起始点 (即停车场入口) , 然后根据用户输入点可以查询从起始点 (入口) 到输入点 (用户所查找车位) 的最短路径, 并将其加粗显示, 如图4。

3.2逆向追踪法显示最短路径

(1) 令Z=X, 把目标点X赋值给变量Z;

(2) 判断变量Z的P值与其相邻点Vi的P值和X到Vi的路径权值之和是否相等。若相等, 则把Vi加入最短路径序列当中;

(3) 判断Vi是否为入口节点。若是, 最短路径查找结束, 显示最短路径序列, 如图4;否则, 把Vi赋值给变量Z, 转步骤 (2) 。

3.3数据处理

系统根据采集到的车位地理位置信息 (经度、纬度) , 把所有车位的最大、最小经度分别记为LOmax、LOmin, 最大、最小纬度分别记为LAmax、LAmin, 然后把点 ( (LOmax-LOmin) /2, (LAmax-LAmin) /2) 与屏幕中心点对应, 系统以此点为参照将用户输入的车位地理位置信息转换为屏幕坐标存放于数据库中, 部分车位的地理信息坐标相对于该点在屏幕中的坐标如表3所示, 表4为部分路段起止及相对权值信息。

4结束语

本文利用Dijkstra的改进算法对停车场车位的带权图进行路径的寻优, 找到从入口到用户所选车位的最短路径。该问题的研究对于现代大型停车场, 特别是在超大型多区域、多层次的大面积多车位、停车路线复杂的停车场, 如能将之与城市停车诱导系统结合起来, 对进入车辆的停放进行引导, 不仅能解决车主寻找车位的盲目性, 还能节省时间和燃油, 且有利于停车场的内部管理, 无论从节约能源, 环境保护和提高停车场的利用率方面, 都具有重要意义。

参考文献

[1]高吕和.基于最短路径的停车场内部诱导系统设计方法研究.北京工业职业技术学院学报, 2007;6 (2) :39—41

[2]王一军, 陶杰.现代大型停车场车位诱导优化算法及仿真.计算机仿真, 2007;24 (11) :176—178

[3]邓博斌.Dijkstra改进算法在地震救援中的应用.Silicon Valley, 2008; (22) :138