基于实际道路网络的三种最快最短路径算法：数据结构和程序外文翻译资料

英语原文共 13 页，剩余内容已隐藏，支付完成后下载完整资料

基于实际道路网络的三种最快最短路径算法：数据结构和程序

F. Benjamin Zhan

Department of Geography and Planning, Southwest Texas State University, San Marcos, TX 78666, USA

fz01@swt.edu

http://www.swt.edu/~fz01/

摘要：众所周知，计算网络中最短路径在许多网络和运输相关的分析中是一个重要的任务。在许多涉及实际道路网络的应用中，从大量的文献提出的算法中选择一个适当的算法，在是一个关键的步骤。在最近的一项研究中，三种在实际道路网络上运行最快的最短路径算法已被证实可行。这三种算法是：1)用两个队列实现的图生长算法，2)用近似桶实现的Dijkstra算法，和3)用双桶实现的Dijkstra算法。作为这项研究的延续，本文回顾和总结了这三种算法，并演示了这些算法的数据结构和程序。本文将尤其对运输，地理信息系统，运筹学和管理科学的研究人员和从业人员非常有用。

关键词：最短路径算法 GIS 运输 网络

致谢：这项研究部分由西南德克萨斯州立大学的一个教职研究增强资金支持，另一部分由环境系统研究所有限公司(ESRI)的一份UNIX ARC/INFO副本支持。作者还希望感谢Boris V. Cherkassky， Andrew V. Goldberg 和 Tomasz Radzik，因为他们提供了一对全最短路径的C源代码。

目录

1. 引言
2. 近来对最短路径算法的评估
   1. Cherkassky 等的评估
   2. Zhan 和Noon的评估
   3. 基于实际道路网络的三个最短路径算法
3. 相关算法的网络表示，标记方法和数据结构
   1. 网络表示
   2. 标记方法
   3. 选择规则和数据结构
4. 双队列实现的图增长算法
5. 用近似桶和双桶实现的Dijkstra算法
6. 结束语

参考文献

1. 引言

随着地理信息系统(GIS)技术的发展，地理信息系统环境下的网络和交通分析已成为许多应用领域的一个普遍做法。网络和传输分析中的一个关键问题是在一个网络中不同位置之间的最短路径计算。有时需要实时完成这个计算。为了例证，让我们来看看一个911呼叫请求救护车将病人迅速送到到医院的案例。在地理信息系统的协助下，确定最快的路线并派遣救护车是有可能的。由于在一个城市的实际道路网络中，一条链路在一天的不同的时间段往往具有不同的拥堵程度，并且一个病人的位置不能被预先知道的，几乎不可能在收到911呼叫之前确定最快的路线。因此，只能实时确定最快路线。在某些情况下，为了确保病人的安全，最快的路线必须在几秒钟内被确定。此外，当大型的实际道路网络被置于应用程序中时，在一个大型网络中最短路径的决策会进行非常密集的计算。由于许多应用程序涉及到实际道路网络，并且计算最快路线(最短路径)需要一个实时的答案，一个自然的问题是：哪一个最短路径算法在实际道路网络上运行最快的？

虽然有数量可观的对最短路径算法性能的实证研究被发表在许多文献中(Dijkstra 1959; Dial等. 1979; Glover等 1985; Gallo and Pallottino 1988; Hung and Divoky 1988; Ahuja 等 1990; Mondou等 1991; Cherkassky 等 1993; Goldberg and Radzik 1993)，但是没有一篇明确的研究论文作为对在实际道路网络哪一个算法或一套算法上运行速度最快的回答。在Zhan和Noon进行的最近一项研究中，(1996)，在实际道路网络中运行最快的三个最短路径的算法已被证实。这三种算法是：1)用两个队列实现的图生长算法，2)用近似桶实现的Dijkstra算法，和3)用双桶实现的Dijkstra算法。作为这项研究的延续，本文回顾和总结了这三种算法，并演示了这些算法的数据结构和程序。

论文的其余部分如下：第2节将简要回顾最近的评估，特别是对15个使用实际道路网络的最短路径算法的评估。第3节将大概回顾代表性网络，标记方法和相关的最短路径算法的数据结构。在4节中详细描述了用两个队列实现的图形增长算法。第5节将回顾用近似和双桶实现的Dijkstra算法。第6节给出结束语。

1. 近来对最短路径算法的评估

一个网络被定义为一个有向图G =(N,A)组成的一组节点集合N和带有相关数值的弧集合A，例如节点的数目n = | N |，弧的数目m = |A|，和连接节点i和j的弧长，记为L(I,j)。最短路径问题可以表述如下：给定一个网络，在这个网络中找到从一个源节点到所有其他节点或节点的一个子集上的最短距离(最小开销)。这些最短路径表示以源节点s为根，带有从s到在网络中任意节点i的唯一路径即到那一点的最短路径的特性的有向树T(Ahuja等 .1993)。从节点s到任何一个节点i的最短路径长度记为d(i)。这个有向树被称为最短路径树。对于具有n个节点的网络，我们可以得到n个不同的最短路径树。在网络中从一个节点(源)到其他所有节点的最短路径通常被称为一对全最短路径。从一个(源)节点到网络节点集合子集的节点的最短路径可以被定义为一对多最短路径。网络中的每一个节点到每一个其他节点的最短路径通常被称为全对全最短路径。

• 1. Cherkassky 等的评估

虽然在一些文献中已经有了发表的对最短路径算法的评估(例如，Glover等1985；Gallo Pallottino 1988；Hung and Divoky 1988)，由Cherkassky 等人. (1993)进行的一项研究是迄今为止最短路径算法的最综合的评估之一。他们评估了一组17个最短路径算法。在他们的实验中，Cherkassky 等人使用C语言编码17种算法，在Sun SPARC-10Workstation对C程序进行测试。一对全的最短路径可以由这些程序计算。读者可以参考Cherkassky 等人(1993)的论文来获取关于实施算法的详细描述。Cherkassky 等人使用了许多的各种复杂程度的模拟网络来评估算法。他们的研究结果表明，没有任何一个的算法在所有模拟网络上表现一致。

• 1. Zhan 和 Noon的评估

最近，Zhan 和 Noon(1996)用实际道路网络测试了17个最短路径算法中的15个。在他们的评估，Zhan 和 Noon丢弃了Cherkassky 等人测试过的17个算法中的2个。他们没有考虑无环路网络的专用算法，因为实际道路网络的弧可以被认为是双向的，因此真正的道路网络包含环路。他们也丢弃了使用堆栈来维护标记节点的实现方式(见下节关于堆栈和标记节点的描述)，因为他们发现在他们的初步测试中，在实际道路网络中，该算法比其他的算法的慢上许多倍。这15种算法都归纳于表1。深入地回顾这15算法不是本文的意图。在Cherkassky 等人(1993)论文和其中的参考文献可以找到对这些算法的详细描述。

在他们的评估中，Zhan 和 Noon使用21个实际道路网络来对最短路径算法进行评估。这21个网络中包括覆盖了美国大陆和20个从美国的中西部和东南部产生的州级道路网络的美国国家公路规划网(NHPN)。这10个州是Alabama (AL)， Florida (FL)， Georgia (GA)， Iowa (IA)， Louisiana (LA)， Minnesota (MN)， Missouri (MO)， Mississippi (MS)， Nebraska (NE) 和 South Carolina (SC)。 20个州级公路网由10个低分网和10个高分网组成。10低分网络包含三个级别的道路，包括州际公路、一级主干道、二级主干道。10个高细节网络包括除了在低分网络中包含的三个层次的道路的一个额外级别的更详细的道路。21网络存储和维护在ARC/INFO GIS，并且在Solaris 2.4环境下的SUN Sparc-20 Workstation运行。节点、弧和弧长是从ARC／INFO下载到ASCII的文件中。在下载前，对其进行了检查来确保网络全互连。

表1 15种被评估的算法总结

在Zhan和Noon的评估中使用的21个网络的总结在表2给出。实际道路网络的一个重要特征是用弧节点比例评估的的连通度。，在表2中可以看到，在21个网络中的节点比例范围是2.66至3.28。和弧节点的比例高达10的模拟网络比较，这21个网络的连通程度和它们差别相当大(参见Gallo Pallottino 1988)。此外，所有21个网络中的连通度没有显着差异。因为在构建一个最短路径树扫描的数目是直接与弧节点比例相关的，观察到弧节点比例在实际道路网络和模拟网络之间的差异是非常重要的。

这15种算法使用C语言编码。这些C程序是基于Cherkassky 等人(1993)提供的一个最短路径C程序的。(1993)。将一组一对全的最短路径的代码进行修改，以自动生成全对全最短路径。这些C程序用版本为2.5.6、带有O4的优化选项的gcc编译器编译的。Zhan和Noon的实验是在SUN Sparc-20 Workstation(具有125MHz的hypersparc处理器，型号HS21和Solaris 2.4环境下运行的64 MB内存)进行。在Zhan(1995)、Zhan和Noon(1996)的论文中，有对这些实验更详细的描述。

• 1. 三种基于实际道路网络的最快路径算法

基于他们的评价，Zhan和Noon建议，解决一对全最短路径问题，最好的实现方式是Pallottino的双队列图形增长算法(TQQ)。他们还建议，当目标是获得一个一对一的最短路径或一个一对多最短路径时，Dijkstra算法提供了一些优势，因为它可以尽快得到最短路径距离目的节点终止(见5节)。詹和中午推荐两Dijkstra算法实现。两者之间的选择取决于最大的网络弧长。他们推荐的近似水桶的Dijkstra算法的实

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[31332]，资料为PDF文档或Word文档，PDF文档可免费转换为Word

您可能感兴趣的文章

• 使用假设检验应用程序对寿命分布的单调方差剩余寿命类别进行非参数检验外文翻译资料
• CAPM：理论有效性、经验难解性与实际应用外文翻译资料
• 几何变换和等效材料在电磁场数值计算中的应用外文翻译资料
• 用TERRA MODIS数据对CBERS-02卫星的CCD相机进行辐射交叉定标外文翻译资料
• 基于RSGIS对城市热岛效应的动态监测和评价方法外文翻译资料
• 人机交互促进发展: 过去，现在和未来外文翻译资料
• 软件工程和软件开发外文翻译资料
• 模拟退火的理论与实践外文翻译资料
• 基于分离估计方法和遗传算法的生物S系统推断外文翻译资料
• 基于Web的空间信息管理系统外文翻译资料