英语原文共 13 页，剩余内容已隐藏，支付完成后下载完整资料
地理信息与决策分析学报，第1卷，第1期。第70-82页，1997年
实际道路网络中最快的三种最短路径算法:数据结构和过程
F. Benjamin Zhan 美国西南德克萨斯州立大学地理与规划系，圣马科斯，TX 78666 fz01@swt.eduhttp://www.swt.edu/~fz01/
摘要
众所周知，网络最短路径的计算是许多网络和交通相关分析中的一项重要任务。从文献报道的众多算法中选择合适的算法是涉及真实道路网络的许多应用中的关键步骤。在最近的一项研究中，已经确定了在真实道路网络中运行最快的三种最短路径算法。这三种算法是:1)用两个队列实现的图增长算法，2)用近似桶实现的Dijkstra算法，3)用双桶实现的Dijkstra算法。作为研究的后续，本文对这三种算法进行了回顾和总结，并展示了与这些算法相关的数据结构和过程。这篇论文对交通运输、地理信息系统、运筹学和管理科学的研究人员和实践者特别有用。
关键词:最短路径算法，GIS，交通，网络
致谢
这项研究得到了西南德克萨斯州立大学教员研究促进基金和环境系统研究所(ESRI) UNIX Arc/Info文件副本的部分支持。作者还要感谢Boris V. Cherkassky、Andrew V. Goldberg和Tomasz Radzik提供了他们的一对多的所有最短路径C源代码。
目录
1. 介绍 1
2. 关于最短路径算法的最近评估 1
2.1 Cherkassky等人的评价 2
2.2詹和努恩的评价 2
2.3现实道路网络中最快的三种算法 3
3.与最短路径算法相关的网络表示、标记方法和数据结构 4
3.1网络表示 4
3.2标注方法 5
3.3选择规则和数据结构 6
4. 用两个队列实现的图增长算法 7
5. 使用近似桶和双桶实现的Dijkstra算法 8
6. 结束语 10
参考文献 11
1. 介绍
随着地理信息系统(GIS)技术的发展，GIS环境下的网络和交通分析已经成为许多应用领域的普遍做法。网络和交通分析中的一个关键问题是计算网络中不同位置之间的最短路径。有时这种计算必须实时进行。为了便于说明，让我们来看一个911报警电话的例子，该电话要求救护车将病人紧急送往医院。今天，在GIS的帮助下，确定最快的路线并派遣救护车是有可能做到的。但是在城市的实际道路网络上，一条路线的交通拥堵程度往往是随着所处时间段的不同而变化的,又因为无法提前得知病人的位置,所以在收到急救电话之前确定最快的路线几乎是不可能的。因此，最快的路线只能实时确定。在某些情况下，最快的路线必须在几秒钟内确定，以确保患者的安全。此外，当应用程序涉及到大型真实道路网络时，确定大型网络上的最短路径在计算上是非常密集的。因为许多应用程序都涉及到真实的公路网，而且最快路径(最短路径)的计算需要实时的答案，所以一个自然的问题是:在真实的公路网中，哪种最短路径算法运行得最快？
虽然大量关于最短路径算法性能的实证研究已经在文献中得到报道(1959年Dijkstra算法;1979年Dial算法等;1985年Glover算法等;1988年Gallo和Pallottino算法 ;1988年Hung和Divoky 算法;1990年Ahuja算法等;1991年Mondou算法等;1993年Cherkassky算法等;1993年Goldberg 和Radzik算法）， 至于哪种算法或一组算法在真实道路网络中运行得最快，目前还没有明确的答案。1996年Zhan和Noon进行了一项最新研究，确定了在真实道路网络中运行速度最快的三种最短路径算法。这三种算法是:1)用两个队列实现的图增长算法，2)用近似桶实现的Dijkstra算法，3)用双桶实现的Dijkstra算法。在此基础上，本文对这三种算法进行了回顾和总结，并给出了相关的数据结构和实现策略。
本文的其余部分组织如下。第2节简要回顾了最近的评价，特别是对使用实际公路网的15种最短路径算法的评价。网络表示，标记方法和数据结构相关的最短路径算法总体在第3节回顾。第4节详细描述了用两个队列实现的图增长算法。第5节回顾了Dijkstra算法的近似和双桶实现。结束语载于第6节。
2. 关于最短路径算法的最近评估
网络被定义为一个有向图G = (N,A)组成的一组节点和一组相关的弧的数值,如节点的数量,n= |N|,弧的数量m = |A|,弧线的长度和连接节点i和j,指示为l(i,j)。最短路径问题可以表述为:给定一个网络，找出源节点到网络上所有其他节点或节点子集的最短距离(最小代价)。这些最短路径代表了一棵源自源节点s的有向树T，其特征是，从s到网络中任意节点i的唯一路径就是到该节点的最短路径(Ahuja算法等， 1993)。s到任意节点i的最短路径长度记为d(i)。这个有向树叫做最短路径树。对于任何有n个节点的网络，可以获得n个不同的最短路径树。从一个(源)节点到网络上所有其他节点的最短路径通常称为一对全的最短路径。从一个源节点到网络节点子集的最短路径可以定义为一对多的最短路径。网络中从一个节点到另一个节点的最短路径通常称为多对多最短路径。
2.1 Cherkassky等人的评价
虽然文献中已经有一些关于最短路径算法的评估报告(例如，1985年Glover等算法 ;1988年Gallo和Pallottino算法；1988年Hung 和Divoky算法），最近Cherkassky等人(1993年)的一项研究是迄今为止对最短路径算法最全面的评价之一。他们评估了17种最短路径算法。在他们的实验中，Cherkassky等人使用C语言编写了17种算法，并在SUN Sparc-10工作站测试了C程序。一对全的最短路径可以由这些C程序来计算。读者可以参考Cherkassky等人(1993)的论文，以获得关于算法实现的更详细的描述。Cherkassky等人使用了大量不同复杂度的模拟网络来评估算法。他们的研究结果表明，没有一种算法在所有的模拟网络中都能一直保持良好的表现。
2.2詹和努恩的评价
最近，詹和努恩(1996)利用真实道路网络测试了17种最短路径算法中的15种。在他们的评估中，詹和努恩放弃了切尔卡斯基等人测试的17种算法中的两种。他们没有考虑非循环网络的特殊用途算法，因为真实道路网络上的弧可以被视为双向的，因此真实道路网络包含循环。他们还放弃了使用堆栈来维护标记节点的实现(有关堆栈和标记节点的描述，请参阅下一节)，因为在初步测试期间，他们发现该算法比实际道路网络上的其他算法慢很多倍。表1总结了这15种算法。本文不打算对这15种算法进行深入的回顾。算法的详细描述可在Cherkassky等人(1993)及其参考文献中找到。
在他们的评估中，詹和努恩使用了21个真实的道路网络来评估最短路径算法。这21个网络包括覆盖美国大陆的美国国家公路规划网络(NHPN)和由美国中西部和东南部10个州的公路网生成的20个州一级公路网。这10个州是阿拉巴马州、佛罗里达州、乔治亚州、爱荷华州、路易斯安那州、明尼苏达州、密苏里州、密西西比州、内布拉斯加州和南卡罗来纳州。20个国家级公路网由10个低细节公路网和10个高细节公路网组成。这10个低细节网络包含3个级别的道路，包括州际公路、主干道和重要干道。这10个高细节网络除了包含在低细节网络中的三层道路外，还包括一层更详细的道路。这21个网络是在Solaris 2.4环境下运行在SUN Sparc-20工作站上的Arc/Info GIS中存储和维护的。节点、弧和弧长从arc /Info下载到ASCII文件中。在下载之前，要检查网络是否完全连接。
表1所评估的15种算法总结
Zhan和Noon使用的21个网络的总结见表2。真实道路网络的一个重要特征是用弧节点比衡量的连通程度。由表2可知，21个网络的弧节点比在2.66 ~ 3.28之间。这21个网络的连通性程度与模拟网络大不相同，模拟网络的弧节点比可高达10 (cf.， Gallo和Pallottino 1988)。此外，所有21个网络的连接程度没有显著差异。由于构建最短路径树的扫描次数与弧节点比直接相关，因此观察真实路网和模拟路网中弧节点比的这种差异是非常重要的。
这15种算法是用C语言编写的。C程序基于Cherkassky等人(1993)提供的一到所有最短路径C程序集。修改了一对一的最短路径C代码集，自动生成all-to-all最短路径。C程序使用gcc编译器版本2.5.6使用O4优化选项编译。詹和努恩的实验是在SUN Sparc-20工作站(型号HS21，在Solaris 2.4环境下运行，具有125MHz的Hypersparc处理器和64兆RAM)上进行的。关于实验的更详细的描述可以在Zhan(1995)和Zhan and Noon(1996)中找到。
2.3现实道路网络中最快的三种算法
根据Zhan和Noon的评价，他们认为解决一对所有的最短路径问题的最佳实现是用两个队列(TQQ)实现的Pallottino的图增长算法。他们进一步表明,如果我们的目标是获得一个一对一的最短路径或一到些的最短路径,迪杰斯特拉算法具有一些优势,因为它一旦获得距离目标节点的最短路径，其余的路径也就可以终止(见第五节)。Zhan和Noon推荐两个Dijkstra算法的实现。这两种实现之间的选择取决于最大网络弧长。他们建议使用Dijkstra算法(DKA)的近似bucket实现来计算最大弧长小于1500的网络上的一对多最短路径。对于弧长大于1500的网络，他们建议也考虑Dijkstra算法(DKD)的双桶实现。
表2评价中使用的21个实际路网概况
注:前10个路网为10个州的低细节路网(三级路网)。其余11个路网是10个高细节路网(4级道路)，分别来自10个州和美国国家公路规划网络(US)。网络是按节点数排序(1996年由Zhan和Noon排序)。
3.与最短路径算法相关的网络表示、标记方法和数据结构
3.1网络表示
输入网络在最短路径算法中的表示和实现方式对算法的性能至关重要。过去的研究已经证明，正向星形表示是表示网络最有效的数据结构(1988年Gallo和Pallottino ;1993年Ahuja等人 35-36页;1993年Cherkassky等)。正向星型数据结构中使用两组数组。第一个数组用于存储与弧相关的数据，第二个数组用于存储与节点相关的数据。所讨论的网络的所有弧都记录在一个列表中，并按照特定的顺序排列。也就是说，从节点1、2、3发出的弧，hellip;，按顺序排列。然而，来自同一节点的弧可以任意排序。与弧相关的所有信息，如起始节点、结束节点、成本、弧长、容量等，都以某种方式存储在弧中(如对应的数组或链表)。
对于节点数组，总共需要n 1个元素。与节点i关联的第i个元素指针(i)存储从节点i发出的第一个圆弧的序号(在上面的圆弧列表中)。有少数例外:1)对于没有出弧的节点i，将指针(i)设置为数组中下一个元素的内容，即，指针(i) =指针(i 1;(2)为为了一致性，采用了以下惯例，即，指针(1)=1，指针(n 1)=m 1。
3.2标注方法
标记方法是大多数最短路径算法的核心步骤((加洛和帕洛蒂诺，1988年;Ahuja等人，1993年，第96页)。标记方法的输出是从源节点s到一组节点的输出树。该最短路径树是迭代构造的，并且操作终止后可以得到s到i的最短路径。在构造最短路径树的过程中，标签法对每个节点i保留三段信息:距离标签d(i)，父节点p(i)，节点状态S(i)。距离标签d(i)存储迭代过程中s到i的最短路径距离的上界。在算法终止时，d(i)表示从s到i的唯一最短路径，父节点p(i)在输出树中记录紧挨着节点i的节点。节点状态S(i)可以是以下状态之一:未到达、临时标记和永久标记。如果在迭代过程中没有扫描某节点，该节点状态为未到达。通常，未到达节点的距离标签设置为正无穷大。当已知当前已知的到达节点i的最短路径也是我们能够达到的绝对最短路径时，节点被称为永久标记。当仍然期望对节点i的最短路径进行进一步改进时，认为节点i只是暂时标记。由此可知，如果节点被临时标记，d(i)是到节点i的最短路径距离的上界;d(i)为到永久标记的节点i的最终最优最短路径距离。
在标记方法迭代开始时，初始化一个有向树，并相应地为源节点S和每个其他节点i设置上述参数d(i)、p(i)和S(i)的初值(Ahuja等人 1993)。在扫描过程中,当扫描节点i时，检查后续节点j的距离标签，尝试降低节点j的距离标签d(j)。如果可以降低d(j)，则通过将j的父节点改为i来更新输出树，即p(j) = i。因为d (j)是已经降低过了的,节点j应该最终成为永久标记。迭代继续进行，直到所有节点都被永久标记。在迭代结束时，输出树变成了一个最短路径树。在形式上，节点i的扫描操作如下所示。
Procedure ScanningOperation(i)
begin
for all
全文共12421字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[214]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
