Dijkstra最短路径算法的一种高效率实现

Dijkstra最短路径算法的一种高效率实现

第24卷第3期武汉测绘科技大学学报Vol.24No.3

1999年9月　JournalofWuhanTechnicalUniversityofSurveyingandMappingSept.　1999

3

Dijkstra最短路径算法的一种高效率实现

乐　阳　龚健雅

(武汉测绘科技大学测绘遥感信息工程国家重点实验室,武汉市珞喻路129号,430079)

摘　要　在已存在的一些最短路径算法测试总结的基础上,根据GIS中网络计算的实际情况,从网络结构的拓扑表示以及Dijkstra算法中快速搜索技术的实现入手,提出了一种Dijkstra最短路径算法的高效率实现方法。

关键词　最短路径算法;网络分析;地理信息系统分类号　P208;O22

　　随着计算机的普及以及地理信息科学的发展,GIS因其强大的功能得到日益广泛和深入的应用。网络分析作为GIS最主要的功能之一,在电子导航、交通旅游、城市规划以及电力、通讯等各种管网、管线的布局设计中发挥了重要的作用,而网络分析中最基本最关键的问题是最短路径问题。最短路径不仅仅指一般地理意义上的距离最短,还可以引申到其他的度量,如时间、费用、线路容量等。相应地,最短路径问题就成为最快路径问题、最低费用问题等。由于最短路径问题在实际中常用于汽车导航系统以及各种应急系统等(如110报警、119火警以及医疗救护系统),这些系统

算单源点到其他所有点间的最短距离;后两种算法则是基于Dijkstra的算法,更适合于计算两点间的最短路径问题[1]。总体来说,这些算法采用的数据结构及其实现方法由于受到当时计算机硬件发展水平的限制,将空间存储问题放到了一个很重要的位置,以牺牲适当的时间效率来换取空间节省。目前,空间存储问题已不是要考虑的主要问题,因此有必要对已有的算法重新进行考虑并进行改进,可以用空间换时间来提高最短路径算法的效率。

1　经典Dijkstra算法的主要思想

Dijkstra算法的基本思路是:假设每个点都

一般要求计算出到出事地点的最佳路线的时间应该在1s～3s内,在行车过程中还需要实时计算出车辆前方的行驶路线,这就决定了最短路径问题的实现应该是高效率的。其实,无论是距离最短、时间最快还是费用最低,它们的核心算法都是最短路径算法。经典的最短路径算法——Dijkstra算法是目前多数系统解决最短路径问题采用的理论基础,只是不同系统对Dijkstra算法采用了不同的实现方法。

据统计,目前提出的此类最短路径的算法大约有17种。F.BenjaminZhan等人对其中的15种进行了测试,结果显示有3种效果比较好,它们分别是:TQQ(graphgrowthwithtwoqueues)、(theDijkstra’salgorithmimplemented

withapproximatebuckets)以及DKD(theDijk2DKA

stra’salgorithmimplementedwithdoublebuck2ets),这些算法的具体内容可以参见文献[1]。其

有一对标号(dj,pj),其中dj是从起源点s到点j的最短路径的长度(从顶点到其本身的最短路径是零路(没有弧的路),其长度等于零);pj则是从求解从起源点s到j的最短路径中j点的前一点。

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]

中TQQ算法的基础是图增长理论,较适合于计点i就被选为最短路径中的一点,并设为已标记

收稿日期:1999201227.乐　阳,女,26岁,硕士,现从事GIS空间分析研究。

　3国家杰出青年科学基金和国家“九五”重点科技攻关资助项目,编号49525101及962B02203。