当前位置: 首页 > >

最短路径算法在交通咨询系统中的应用_图文

发布时间:

开发与应用

计算机与信息技术

·23·

最短路径算法在交通咨询系统中的应用

高寒弢 秦士琨 刘元梓
(61920 部队,四川 成都 610505)

摘 要 最短路径问题在交通调度、车辆导航等实际应用中有着重要的意义。本文阐述了迪杰斯特拉算法求最短路径
的方法,并给出了迪杰斯特拉算法在交通咨询系统中的应用实现方法。
关键词 最短路径;最短路径应用;交通咨询;Dijkstra 算法

1 引言
最短路径问题在计算机科学、运筹学、交通工程学、地 理信息系统等学科中是一个研究的热点,它是资源分配、线 路选择等问题解决的基础,尤其是在诸如地图、车辆调度和 路由选择方面有着广泛的应用。本文就最短路径算法在交通 咨询系统中的应用进行了分析和实现。
2 最短路径算法
在求解网络图中节点间最短路径的方法中,目前国内外 一直公认的较好的算法有迪杰斯特拉(Dijkstra)算法和弗洛 伊德(Floyd)算法及启发式 A* 算法。前两种算法中,网络被 抽象为一个图论中定义的有向或无向图,并利用图中节点邻 接矩阵记录点间的关联信息。在进行图的遍历以搜索最短路 径时以该矩阵为基础不断进行目标值的最小性判别,直到获 得最后的优化路径。启发式 A* 算法采用一个代价函数,只有 代价函数范围内的点才会被遍历,可以有效地缩小搜索的 范围。 2.1 算法原理
本文中在求解地图中节点间的最短路径时,采用的是经 典的迪杰斯特拉算法,下面介绍迪杰斯特拉算法的原理与 实现。
迪杰斯特拉算法提出的是一种求从某个源点到其余各顶 点的最短路径的算法。算法的基本思想是:按照路径的长度 不减的原则产生最短路径,即从源点到其余各顶点的各条最 短路径中,首先产生距离源点最近顶点的最短路径,然后产 生次短的最短路径,以此类推最后产生那条最长的最短路径。
下面就详细说明迪杰斯特拉算法的实现原理。 为说明算法的原理,首先,引入一个辅助向量 D ,它的 每个分量 D[i] 表示当前所找到的从始点到每个终点 v 的最短

路径长度。它的初态为:若从 v 到 vi 有弧,则 D[i] 为弧上的
权值;否则置 D[i] 为 ∞ 。显然,长度为

D[

j]

=

Min
i

{D[i] | vi

∈V}

的路径就是从 v 出发的长度最短的一条最短路径。此路径为

( v , v j )。 那么,下一条长度次短的最短路径是哪一条呢。假设该

次短路径的终点是 vk ,则可想而知,这条路径或者是( v , vk ),或者是( v , v j , vk )。它的长度或者是从 v 到 vk 的 弧上的权值,或者是 D[ j] 和从 v j 到 vk 的弧上的权值之和。
一般情况下,假设 S 为已求得最短路径的终点的集合,

则可证明:下一条最短路径(设其终点为 x )或者是弧( v ,

x ),或者是中间只经过 S 中的顶点而最后到达顶点 x 的路

径。

因此,在一般情况下,下一条长度次短的最短路径的长

度必是

D[

j]

=

Min{D[i] | i

vi

∈V

?

S}

其中, D[i] 或者是弧( v , vi )上的权值,或者是

D[k](vk ∈ S) 和弧( vk , vi )上的权值之和。

根据以上分析,可以得到如下描述的算法:

(1)假设用带权的邻接矩阵 arcs 来表示带权有向图

arcs [i][ j] 表示弧< vi , v j >上的权值。若< vi , v j >不存在, 则置 arcs [i][ j] ∞(在计算机上可用允许的最大值代替)。S

为已找到从 v 出发的最短路径的终点的集合,它的初始状态

为空集。那么,从 v 出发到图上其余各顶点(终点) vi 可能
达到的最短路径长度的初值为:

D[i] = arcs[LocateVex (G, v)[i]]
(2)选择 v j ,使得 D[ j] = Min{D[i] | vi ∈V ? S}

vi ∈V

·24·

计算机与信息技术

开发与应用

v j 就是当前求得的一条从 v 出发的最短路径的终点。令 S = S ∪ { j}

(3)修改从 v 出发到集合V ? S 上任一顶点 vk 可达的最 短路径长度。如果

D[ j] + arcs[ j][k] < D[k]

则修改 D[k] 为

D[k ] = D[ j] + arcs[ j][k ]

(4)重复操作(2)、(3)共 n-1 次。由此求得从 v 到图

上其余各顶点的最短路径是依路径长度递增的序列。

2.2 示例 如图 1 所示的是一个带权有向图,通过应用上述最短路

径算法,可以得到由图 1 中任一顶点到其余各顶点的最短路

径。表 1 是以 v0 点为例,从 v0 点到其余各顶点的最短路径以 及路径长度。

表1

始点 终点

最短路径

路径长度

v1

v2

v0

v3

v4

v5



( v0 , v2 )

10

( v0 , v4 , v3 ) 50

( v0 , v4 )

30

( v0 ,v4 ,v3 ,v5 ) 60

上述功能。本文采用 VC6.0 进行编程,程序具体实现流程如 图 2 所示。
开始
载入地图文件
选择起点和目标点

从未搜索点中求出前驱点

更新前驱数组

N

从未搜索点集合中除去已经记录的前驱点

搜索完所有点
Y
在得到的前驱数组中找到从起点到目标点的最短路径
绘制该最短路径

结束

图1 例如,由图 1 和表 1 可以看出,由 v0 点到 v3 点有多条路 径,但通过最短路径算法可以得出,由 v0 点到 v3 点的最短路 径为 v0 — v4 — v3 ,路径长度为 50。
3 迪杰斯特拉算法在交通咨询系统中的实现
由上所述,可以看出迪杰斯特拉算法是一种经典的最短 路径算法,运用它可以在交通咨询系统中快速、有效的实现 最短路径的查询。通过运用迪杰斯特拉算法编程,可以实现

图 2 程序流程 程序开始运行后,首先需要载入地图文件,读取后生成 距离矩阵,然后选择出发点和终点,应用上述最短路径算法, 即可求出从出发点到终点的最短路径及路径长度。 图 3 为一幅地图数据文件,图 4 为载入地图文件后,选 择出发点为成都,终点为天津后,通过最短路径算法求出 的从成都到天津的最短路径为:成都—西安—郑州—北京 —天津。
4 结论
应用迪杰斯特拉算法可以方便快捷的求出距离矩阵中 各点之间的最短路径,运用到交通咨询系统中,可以为客户 提供交通走向、路径选择、行程安排等服务,并可协助进行 交通分析和调度,在交通咨询系统中能发挥重要作用。

开发与应用

计算机与信息技术

·25·

图 3 地图原始数据图
参考文献
[1] 方美红,刘少华. 基于VC++的最短路径算法设计与 实现.城市勘测,2008,1:43-46
[2] (美)Hamdy A.Taha.运筹学导论:初级篇(第8版). 北京:人民邮电出版社,2008
[3] (美)Cormen T.H.. 算法导论(第2版). 北京:机 械工业出版社,2006
[4] (美)Alan Tucker. 应用组合数学(第5版). 北京: 人民邮电出版社.2009
[5] 彭飞,柳重堪,张其善.车辆定位与导航系统中的快 速路径规划算法.北京航空航天大学学报,2002,28(1):70-73
[6] 付梦印,李杰,邓志红.限制搜索区域的距离最短路

图 4 最短路径示例(成都—天津) 径规划算法.北京理工大学学报,2004,24(10):881-884
[7] 严寒冰,刘迎春.基于GIS的城市道路网最短路径算 法探讨.计算机学报,2000,23(2):210-215
[8] 孙鑫,余安萍.VC++深入详解.北京:电子工业 出版社,2006
收稿日期:8 月 16 日 修改日期:9 月 20 日 作者简介:高寒弢(1984-),男,助理工程师,四川金 堂人,主要研究方向为卫星导航技术与应用;秦士琨(1982-), 男,硕士,助理工程师,山东济宁人,主要研究方向为卫星 导航技术与应用。

(上接第 22 页)
参考文献
[1] Elliott D.Kaplan.GPS 原理与应用[M].电子工业出版社, 2002,8
[2] 冯燕侠,方涛.用 VB 实现 GPS 接收机与计算机的串 口通信[J].电脑编程技巧与维护,2004,12

[3] 范逸之,陈立元.Visual Basic 与 RS-232 串行通信控制 [M]. 清华大学出版社,2002.6
收稿日期:7 月 14 日 修改日期:8 月 12 日 作者简介:刘静(1985-),女,硕士研究生,山东科技 大学,研究方向:分布式系统理论与算法。




友情链接: