英语原文共 29 页
一对一最短路径问题：双树Dijkstra算法的实证分析
RICHARD V. HELGASON和JEFFERY L. KENNINGTON 南卫理公会大学计算机科学与工程系，达拉斯，tx 75275-0122
B. DOUGLAS STEWART 阿拉巴马大学工业工程系，塔斯卡卢萨，al 35406-0288。 1992年1月20日收到；1992年12月17日修订
摘要
针对起点到终点最短路径问题，提出了四种新的最短路径算法，即两种序列算法和两种并行算法，并与文献中讨论的五种算法进行了实证比较。新的算法s22结合了Dial等s2算法的高效数据结构，同时从源节点和汇聚节点构建最短路径树的思想，被认为是最快的顺序最短路径算法。新的并行算法PS22基于s22，是最好的并行算法。我们也给出了三个新的s22型最短路径启发式的结果。这些启发式算法发现非常好的(通常是最优的)路径比最好的最短路径算法快得多。
关键词：最短路径，并行算法。
自50年代末首次提出求解方法以来，最短路径问题已成为组合优化、计算机科学和运筹学等领域的基本问题之一。算法和应用在这些领域的重要书籍中很常见(如[1,2,12,18,19,21,24,27,28,29])。这一问题的研究既有其优美的数学结构，也有其众多的实际应用。我们最近对这个问题的兴趣是由于我们在多指令、多数据(MIMD)并行计算环境中开发的几个数学优化过程中需要解决最短路径子问题。
在[4,13]中可以找到关于许多最短路径问题变化的优秀调查。技术的调查和计算比较可以在[5,7,8,10,14,15,16,20]中找到。这些方法分为两大类:标签设置算法和标签校正算法。Dijkstra[9]被认为是第一个标签设置算法，使用这种方法的任何算法都被认为是Dijkstra原始算法的特定实现(参见Gallo和Pallottino[13])。
典型的，最短路径问题是一个需要从单个源节点（如S）到网络中所有其他节点的最短路径的问题。该解可以表示为根在S上的最短路径树。在本文中，我们关注的是在源节点和接收器节点之间寻找最短路径的问题，T.Dantzig[3]建议建造一对树，其中一棵扎根于S，另一棵扎根于T，没有给出停止的标准。这一策略也出现在书中，由Berge和古伊拉小时[1]与错误的停止标准。尼科尔森是第一个提出正确分析二树算法的人。hart等人提出了一种利用启发式成本函数的一树算法。其中包括节点间距离的下限可用的情况，并证明了得到了最优路径。pohl[26]将这些结果推广到双向算法，前置摩尔和Pasche[22]，他们提出了类似的结果。在德雷福斯的调查中还可以找到更多的讨论，他推测用S和T建造树木对这个问题是无效的。
文献中对两树算法的实证研究较少。Pohl[25]给出的结果很少得到认可，直到最近才有进一步的研究出现。Mohr和Pasche[22]利用二树Dijkstra算法和他们的二树算法(适用于具有下界的网络)求解了三个网格网络和一个代表瑞士路线图的网络中的最短路径。如果有两个处理器可用，他们还模拟了并行算法的结果。
这项研究的目的是使用比传统Dijkstra算法更有效的数据结构实现两棵树算法，并使用两个处理器实际解决最短路径问题。开发了四种新的算法:基于Dial [6] (Dial 等[7]中的S1代码)的顺序和并行二叉树算法，以及基于Dial 等.[7]中的s2代码的顺序和并行二叉树算法。将这些代码与经典的Dijkstra、S1、s2、二树Dijkstra和并行二树Dijkstra代码进行比较。
算法
本节介绍定义、符号和九种算法，它们代表了我们在计算研究中使用的代码。符号和表示是基于在[14]中找到的。每个算法的输入是一个有向图G = [N, a]，有一个节点集N和一个弧集a。两个节点s和t之间需要一条最短路径，假设存在这样一条路径。
我们还假设对于所有的算法所有的(i, j)EA，liy gt;_0。为了有效的实现，假设G是以电弧表的形式给出的。
每个算法的基本工作实体包括一组标签du，表示从最短路径树T的根到节点的距离;树中节点的一组前辈pu;以及候选节点集合Q。在基于S1和S2算法的算法中，集合Q将被划分为子集，或称为bucket，其中包含与根节点距离相同的候选节点。这要求每个弧长都是整数，以对应于一个索引。
经典Dijkstra算法
Dijkstra的经典算法[9]从节点s开始，构建一个最短路径树T，其中s到树中任意节点的最短路径已知。当节点t被放置在树中时，我们有一个从s到t的最小长度的有向路径，并且可能终止。如前所述,这里讨论的算法不同的候选节点放置在和从集合中检索:经典的迪杰斯特拉算法的实现(D1)搜索候选节点的列表,Q,最低标签节点并将所有此类节点的集合R中的所有节点可以被一个接一个扫描。当有许多节点使用最小的标签绑定时，只需最小的努力就可以避免搜索。算法可表述如下:
1.2．S1的算法
这个单树算法是通过Dial[6]实现的。与算法D1一样，它选择最小标签节点扫描每个迭代，但是Q中的节点根据距离标签存储在bucket中。需要更具体地说,Imax 1列表,Imax = max { l ~:(u,v)E }和节点u是存储在列表z如果d = z(mod Imax 1)。只有节点相等距离标签将在列表z和只有Imax 1列表是必需的,因为一个节点u用最小的标签,我们有,对于每个v ~ Q,du lt; dv lt;杜 hnax。bucket作为双向链表能够有效地实现。从最小标签节点u开始，下一个非空列表包含下一个最小标签节点，像算法D1那样搜索整个列表的工作量大大减少。权衡的结果是，每当一个节点有一个改进的距离标签时，管理双向链表的工作量就会增加。算法可表述如下:
1.3．S2的算法
他的单树算法基于Dantzig[3]的思想，这里是由Dial等人实现的[7]。它要求所有uisin;(u)N的每个FS（u）是最短的一阶排序。考虑到这个，观察可以让节点的整个前星不需要同时扫描所有的节点，比如，v，这是第一次更新时的距离标签小于或等于从节点u更新的任何节点。
节点v被放置在单向链表中，与u成对，处于du luv级别。在说明下面的算法时，我们使用k(u)作为计数器来指向F S (u)中要扫描的下一个弧。节点wk(u)为弧的对应节点。每个正向弧列表的长度由h(u)给出。应该注意的是，实际的实现不使用计数器。前向星形数组中的一个简单减号可以指示下一个要扫描的弧。链表上的节点可能重复，因此不需要删除。即使这样，链表上的节点数量也不会超过节点总数，因为每个扫描节点只允许有一个节点。Q在算法$1中搜索下一个非空列表和最小标签节点。如果节点的成对前任不是它的当前前任，那么该节点已经在最短路径树中，可能会被丢弃。算法可表述如下(见Gallo和Pallottino [13]):
1.4．二树Dijkstra算法
二叉树Dijkstra算法构建了一对最短路径树，一棵从s开始，一棵从t开始。以t为根的树与以s为根的树类似，但扫描的是向后的恒星，其前身是弧线的头部，而不是尾部。这两棵树以交替的步骤生长，当两个树中都出现节点时触发终止。但是，应该注意的是，出现在两个树中的节点不一定是在最短路径上(有关终止条件的证明，请参见[23])。对随机图的测试表明，这个节点在最短路径上的时间约为72%。在两个树的节点上执行搜索，以找到一个节点，比如r，使得d~ d,t是最小的。从s到t的最短路径可以通过在每棵树中分别从r到s和从r到t的前两棵树找到。我们将J定义为一组节点，这些节点可用于标识最短路径。该算法需要两倍于算法D1的存储，并且可表述为：
1.5．二树S1算法
两棵树S1算法构建一对最短路径树，一棵来自s，一棵来自t，每棵树使用$1的数据结构。在算法D2中，当第一次在两个树中发现一个节点时，终止被触发。令d~ d~最小的节点r给出了s到t的最短距离，且位于最短路径上。该算法需要两倍的$1存储，可表述如下:
1.6．二树S2算法
和前面的二树算法一样，二树S2算法使用镜像S2数据结构构建两个最短路径树。首先，我们期望停止过程与之前的两棵树算法相同，即当一个节点在两棵树中的时候，求出所有i E t t UT t的最小值d~ d~t。然而，当一个节点第一次被放置在它的第二棵树中时，我们还没有准备好搜索这样一个最小的双标记节点。在[23]中，这样的节点被证明是在最短路径上的，因为这两棵树中的每个节点都有一个完整的扫描弧列表。在每个树的S2实现中，情况并非如此。事实上，这就是单树S2算法的优点。在两个方向，我们必须执行额外的扫描，以满足尼克尔森标准;但是，我们不需要管理链表。所需要的是更新距离标签和之前的标签。实际上，我们只需要从每个弧列表中扫描弧的子集。Nicholson证明了当一个节点在两棵树中都是第一个时，任何不在这两棵树中的节点都不会在最短路径上。如果将弧扫描到这些节点，它们仍然不在树中或最短路径上，因此更新距离标签将是徒劳的。这些节点也构成了arc列表的大部分。在清理阶段唯一需要扫描的弧是那些具有从一个树中的节点到另一个树中的节点的弧。由于这些弧线可以从任意一个节点进行扫描，因此考虑来自较小树中的节点的这些弧线更为有效。在更新距离标签和之前，我们准备搜索最小的双标记节点，以找到从s到t的最小距离和最短路径。算法可表述如下:
1.7．并行二树Dijkstra算法
不难看出，在两树最短路径算法中，树之间是相互独立的。唯一的要求是检查一个节点是否在相反的树中。此只读步骤使用多个处理器不会造成干扰。这就导致了最简单的异步并行应用程序，它使用两个处理器，每个处理器对应一个树。当一个处理器识别出两个树中的一个节点时，它会设置一个标志，告诉另一个处理器在执行相同操作时，在其树中找到最小的双标记节点。两者的最小值是s到t的最小路径距离。同样，从最小双标签节点开始的前一个标签中隐含了一个最短路径。在下面的算法中，每个处理器都有自己的识别号procid。称为fork(2)的并行处理构造表明，在到达连接构造之前，将使用两个处理器来执行这些部分。算法可表述如下:
1.8．并行二树SI算法
并行二树S1算法类似于并行二树Dijkstra算法。每个处理器分配一个节点s或t，并使用S1数据结构构建树。当发现两个树中都有一个节点时，将设置一个标志，告诉两个处理器在各自的树中找到最小的双标记节点。这两个的最小值给出了从s到t的最小距离路径，路径隐含在前一个标签中。算法可表述如下:
1.9．并行二叉树S2算法
与前面的并行算法一样，并行二树S2算法分配一个处理器处理以s为根的树，另一个处理器处理以t为根的树。当一个节点第一次出现在两个树,一个标志被设置为启动扫荡节点扫描阶段。如第1.6节所述，我们仅从较小的树执行扫荡扫描阶段。要在两个处理器上执行此工作，每个处理器都需要共享相同的数据，即距离标签。为了防止可能的相互干扰，使用了称为锁的并行处理结构，这样每次只有一个处理器可以更新距离标签。然后，同步处理器，并为每个树找到最小的双标记节点。这两个的最小值给出了从s到t的最小距离路径，而最短路径隐含在前面的标签中。SINSERT(x)和TINSERT(x)的步骤见第1.6节。该算法可以表示如下
计算经验
所有九种算法都用FORTRAN编写，并使用一个或两个Intel 80386处理器在顺序对称S81上运行。有几个因素会影响最短路径代码的性能。首先，节点数量对于dijkstra类型的算法很重要，这种算法的主要工作是在节点长度数组中搜索最小标签节点。其次，平均度(A/N)很重要，因为dijkstra类型和sl类型的算法必须在每次迭代中扫描整个正向(或反向)星星，而s2类型的算法通常只扫描子集。最后，网络的代价范围影响到sl和s2类型算法的Q数组的长度和稀疏性，这两种算法在每次迭代中都要搜索。成本范围和程度还会影响与最小距离标签相关联的节点数量，从而减少搜索的数量。
选择了4个节点级别(1,000、2,000、3,000、4,000)、10个平均学位级别(5,10,15,20,25,50,75,125,100,125,150)和3个成本范围(1-100,1-1000,1-10,000)，以证明哪些因素影响性能。产生的随机网络总数为120个。每个代码使用相同的随机生成的s和t节点解决每个网络的20个问题，总共产生2400个问题。表1-3中的每个数据点是解决这20个问题的时间之和(以秒为单位)。由于s2型编码需要对前向和后向星进行排序，因此所有编码都被赋予了对前向和后向星进行排序的功能，以消除这一相对因子。排序时间是否应该与s2类型的算法一起计算是有争议的，因为它需要排序的弧列表。在这里，我们简单地假设数据按预定顺序可用，并承认如果数据不可用，那么s2类型的算法就不合适。
通过9个编码和120个网络，可以进行许多比较和观察。我们强调主要的兴趣点。首先，与之前的研究有一些重叠，我们希望确认之前的结果。在[8]中，我们发现S1在最小次问题上优于$2。随着前向恒星变得更大，只扫描一个子集的节省就实现了。Mohr和Pasche[22]在4个高节点数、低阶网络上发现，d2型算法所需时间约为D1算法所需时间的38%。在这里，我们发现D2的平均值分别为65%、49%和23%，而D1的成本范围分别为1-100、1- 1000和1- 10000。
在并行的二叉树$2代码中PS22是总赢家。在120个网络中，它在108个网络中最快，而PS12在12个网络中最快。在成本范围为1-100的网络中，当平均度高于10时，PS22是最快的代码;在成本范围为1- 1000的网络中，当平均度高于5时，PS22是最快的代码。当成本范围为1-10,000时，它总是最快的代码。PD2对节点数最少、成本最低、程度最高的网络进行了改进，所有
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
