动态Dijkstra算法实现动态最短路径

沙特国王大学学报动态Dijkstra：一种基于回溯优先级队列苏尼塔a，迪帕克·加格ba计算机科学与工程，Thapar大学，Patiala 147004，印度b BennettUniversity，Greater Noida，Bennett University，Noida 201310，India计算机科学工程系阿提奇莱因福奥文章历史记录：2017年10月31日收到2018年3月2日修订2018年3月3日接受在线发售2018年保留字：数据结构算法动态最短路径回溯数据结构A B S T R A C T动态最短路径算法是用来适应底层图拓扑结构的在线更新操作序列，并方便后续查询操作的算法。对于该问题的不同版本，存在许多解决方案，所有这些解决方案都识别其最短路径可能受到变化影响的顶点集，然后根据更新序列更新其最短路径。在本文中，我们动态Dijkstra算法，有助于有效地解决动态单源最短路径问题。通过使用追溯优先级队列数据结构来实现动态化回溯数据结构一步一步地识别受影响的顶点集，从而有助于以最少的计算次数来适应变化。因此，与一个合适的动态图表示和使用追溯优先级队列，我们提出了算法动态Dijkstra算法给出的解决方案的动态单源最短路径问题的复杂性为O（nlg m）的更新时间。我们已经进行了实验分析，通过比较所提出的算法与其他算法的性能。实验结果表明，该算法在时间和内存使用方面具有更好的性能©2018制作和主办由Elsevier B.V.代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍一般的图问题可以是静态的也可以是动态的。动态图问题是指底层图在其不同参数（如边、顶点或权）的更新方面没有限制的问题这些问题是更具挑战性和耗时相比，静态的。动态最短路问题是研究最广泛的动态图问题之一。最短路径问题是一个在运筹学、管理系统、计算机科学和人工智能等许多不同领域都有应用的通用问题。它在如此不同的领域中使用的主要原因是，基本上任何组合优化都是*通讯作者。电 子 邮 件 地 址 ： sunita. gmail.com （ Sunita ） ， deepakgarg108@gmail.com（D.Garg）。沙特国王大学负责同行审查制作和主办：Elsevier这个问题可以被表述为最短路径问题（Rana和Garg，2014; Sarnak和Tarjan，1986; Yigit和Unsal，2016）。动态单源最短路问题是一类动态最短路问题，它给出了从在动态空间中，一个源顶点到一个图的所有其他顶点。以往求解动态单源最短路径问题的方法都是基于确定所有可能受图中给定变化影响的顶点，然后相应地更新最短路径。解决这个问题的另一种方法是使Dijkstra算法动态化.静态Dijkstra算法是一种迭代算法，用于找到从图的特定顶点（称为源顶点）到图的所有其他顶点的最短路径（Dijkstra，1959）。该算法的工作可以数学地表示为：如果d½u] wu;vd½v]然后d½v]<$d½u] wu;v其中d[u]表示顶点u到源顶点的估计距离，w（u，v）表示边（u，v）的权重。在基本算法中使用的数据结构是优先级队列。为了使算法动态化，我们使用了新的数据结构范式，即由https://doi.org/10.1016/j.jksuci.2018.03.0031319-1578/©2018由Elsevier B. V.代表沙特国王大学制作和主办。这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comSunita，D. Garg/沙特国王大学学报-计算机与信息科学33（2021）364-373365Demaine et al.（2007）为此目的。Kanat Tangwongsan（Acar等人，2007年）引入了这些数据结构的一个变体，称为作为非遗忘的追溯（主动）数据结构。在追溯性数据结构中，由于过去的某些修改而在数据结构中产生的改变被自动地容纳在当前，但是在非遗忘追溯性中，改变被逐个传播，即，用户被告知由于过去进行的修改而实现的第一操作。我们基本上使用活动数据结构（即。e.非遗忘的追溯力）来解决我们的问题。在本文中，我们将不被遗忘的回溯数据结构称为回溯数据结构。本文所做的主要工作是：本文提出了一种新的动态最短路问题的求解方法，该方法利用回溯数据结构将动态最短路问题的静态算法动态化为了使算法动态化，我们给出了一个使用红黑树的回溯优先级队列的实现我们已经验证了我们的方法的正确性与一个例子图的帮助。我们已经实现了所提出的算法，并进行了实验分析，通过比较所提出的算法与其他算法的性能。本文的组织如下：第2节回顾了本文中使用的基本术语和符号。第三部分介绍了本文的工作，并给出了算法和理论验证的帮助下，一个例子图。第4节描述了实验分析。最后，第五部分对工作进行了总结。2. 相关工作动态最短路问题分为半动态和全动态两类.半动态可以是递增的或递减的。增量意味着只允许插入/边权重减小，而减量意味着只允许删除/边权重增大。完全动态问题可以应用这两种类型的更新操作。一些作者还考虑了更新操作的数量作为这类问题的分类标准，并提出了可以一次处理单个更新操作的问题的解决方案（Burlington等人，2003; Frigioni等人，2000; Xiao等人，2004年）。在（Narviaez等人，2001; Ramalingam和Reps，1996），其允许将更新操作作为批处理。作者也提出了许多方法来解决问题的半动态和全动态变体，如Gallo（Gallo，1981）和Fujishige（Fujishige，1981）给出了半动态增量问题的解决方案，Even和Shiloach（Even和Shiloach，1981）给出了递减情况下的O（mn）更新时间算法Ramalingam和Reps（Ramalingam和Reps，1996）给出了用于增量变量的广义算法，该算法被证明是实践中最好的算法（Burlington等人，2003年;Demetrescu和Italiano，2006年），尽管其最差情况复杂度较高。Ramalingam和Reps算法背后的想法是识别受影响的节点/顶点的集合。这组受影响的节点被进一步分为两个不同的集合。一个集合表示那些受影响的节点，其最短路径不能使用最短路径树的当前拓扑这组节点存储在队列（Q）中。另一组受影响的节点是其更新的最短路径可以从最短路径树的当前拓扑计算该集合以堆（H）数据结构维护队列（Q）中的节点的最短路径使用堆（H）中的节点该算法是迄今为止图1.一、Ramalingam和Reps方法的最短路径树表示实际上是最好的一个，并且已经用于解决许多动态图问题，如中间中心性（Bergamini和Meyerhenke，2015; Bergamini等人，2015; Kas等人，2013年，2014年）。图1显示了在Ramalingam和Reps算法中生成的最短路径树如何在边（u，v）权重递增后用于识别受影响的顶点由于更新，顶点u的最短路径树中未受影响的顶点表示为虚线。顶点v和x之间的红色虚线表示它不再是最短路径（在边（u，v）更新后）。因此，标识了替代最短路径（其是边（n，x），并且现在边的最短路径树是顶点m而不是顶点u的最短路径树的一部分（如更新之前）。此外，King和Thorup（King and Thorup，2001）给出了上述算法的特殊化。他们建议使用最短路径树的变体。在这个最短路径树中，每个节点在维护最短路径的同时，也维护一个指向下一个最短路径的特殊链接。存储这个特殊树的优点是能够找到替代路径，而不需要探索集合中的所有传出弧此外，Demterscu et al.（Demetrescu和Italiano，2003）提出使用更简单的机制来识别属于队列（Q）的受影响节点的集合。算法的其余部分与Ramalingam和Reps相同因此，在该算法的情况下的队列大小可能大于Ramalingam和Reps算法的队列Thorup（Thorup，2004）提出了一种求解全动态最短路径问题的方法，其时间复杂度为O（n2（logn+log2（（m+ n）/n））的平均更新时间，比最佳情况时间O（n2）至少有log因子的改进。研究人员的注意力转向这些问题的近似算法（Bergamini等人，2015年; Bernstein和Roditty，2011年; Bernstein，2013年;Burnstein等人，2003; Henzinger等人，Roditty和Zwick（Roditty和Zwick，2012）的开创性论文证明了O（mn）更新时间对于精确距离是最佳的，因此几乎没有改进现有方法的余地。Mostafa Dahshan（Dahshan，2013）也给出了修改的Dijk-stra3. 建议的工作：使用回溯性动态Dijkstra算法求解最短路径问题在本文中，我们提出了动态的Dijkstra算法使用追溯数据结构。这些数据结构有助于在数据结构上维护事件的历史顺序。因此，这些可以有效地用于静态算法的动态化。由于在算法的静态实现中使用了优先级队列，因此使用回溯优先级队列可以使算法动态化。对于用Dijkstra算法和回溯优先队列求解动态最短路问题，●●●11366Sunita，D. Garg/Journal of King Saud University- Computer and Information Sciences 33（2021）364- 373需要实现追溯优先级队列和适当的动态图形表示。首先，我们给出了在整个文件中使用的基本符号。然后，我们定义如何Dijkstra可以通过替换数据结构，即动态。优先级队列通过追溯优先级队列。然后给出了底层动态图的表示方法和基于高度平衡树的回溯优先级队列的实现细节在下一节中，我们将指定需要添加到静态Dijkstra中以将其转换为动态对应物的步骤。3.1. 基本符号设G =（V，E，w）是一个简单有向图，其中V和E分别是顶点集和边集，w是从E到非负实数集的函数，即w给出相应边的权。设e =（u，v）eE，则u为e的头部表示为eh，v是e的尾部表示为et。每个顶点v由一个键（如a，b等）表示，每个边e（如（a，b），（a，c）等）也是如此。图中的边e（u，v）被赋予权重w（u，v）。 每个顶点v包含辅助信息诸如估计距离，其表示该顶点距源顶点的预测最短距离，并且预测最短路径前驱给出该顶点在预测最短路径上的直接前驱对于动态最短路问题，我们认为边权的变化可以是边权只增加或边权只减少或边权既增加又减少的任意形式。虽然我们只考虑边的权重变化，但是边的插入/删除也可以通过这些来处理，因为边的插入可以被认为是边的权重从减少到插入边的权重。同样，边删除可以被认为是边权重的增加，通过将删除边的边权重更改为。现在，我们解释优先级队列，设Q是一个追溯优先级队列。Q中的条目具有（ver，ins_time，dist，pred，del_time）的形式，其中ver是顶点，ins_time是该节点已被插入队列中的时间，dist包含该顶点距源顶点的估计最短距离，pred是该顶点在预测最短路径上的前驱顶点，del_time是节点从队列中删除的时间。队列中的节点基于两个参数进行排名：首先根据距离值（dist），然后根据时间。如果多个条目具有相同的dist，则它们之间的顺序是任意的。Q支持不同的操作，在第3.2.2节中有详细说明。由于我们是动态Dijkstra算法，所以我们需要一个图形表示，有效地适应动态更新的边缘权重。我们选择了一个简单而有效的代表我们的目的。该图使用邻接矩阵表示，该邻接矩阵将图存储为邻居矩阵（假设没有新的顶点添加到图中）。毫无疑问，在底层图稀疏的情况下，表示将是昂贵的，但是在这种表示中，任何更新都可以在恒定的时间内执行，因此在这种表示中改变图结构非常容易。因此，我们选择了这样的表示，使得时间边界不会因为需要在图上进行的更改而受到影响。3.2. 使用平衡搜索树的为了动态Dijkstra算法，我们希望保持一组最短路径的图，其边的权重变化，因此在最短路径中选择的边的优先级随着时间的推移而变化。因此，为了这个目的，我们使用追溯优先级队列，它允许在任何时间点执行opeartions。简单优先级队列的所有操作都是在追溯优先级队列，即操作Insert和Del_min可以随时调用和撤销。因此，为追溯优先级队列定义的主要操作如下：插入（Insert（x，t））：在时间t执行项x的插入，即在时间t根据其优先级值将新元素x插入到优先级队列中删除（Del_min（t））：在时间t执行从优先级队列中删除最小值。Revoke（Insert（t））：撤消在时间t执行的插入操作。Revoke（Del_Min（t））：撤消在时间t执行的删除操作。这相当于将在时间t删除的项再次插入优先级队列。Find_min（t）：返回时间t时优先队列中存在的最小元素。这些操作的详细算法在下一小节中给出。取消操作意味着在当前或过去的任何时间执行操作，而撤销操作意味着撤消操作在过去某个时间进行的操作。操作时间的联系被操作顺序中的顺序打破。在操作中使用的时间参数t允许保持操作的历史顺序。在本节的剩余部分，我们将简要回顾平衡二元搜索树，以及如何使用这些树实现追溯优先级队列数据结构。3.2.1. 高度平衡搜索树高度平衡的二叉搜索树是一种二叉搜索树，在存在在线插入和删除项的情况下自动保持其高度（即平衡其高度）较小。这些二叉树通过在关键时刻对树执行变换（例如树旋转）来平衡高度，以保持高度与log2（n）成比例。毫无疑问，在执行这些转换时会涉及到开销，但它可以通过快速执行所有其他操作来克服（Knuth，1998）。已经定义了各种高度平衡二叉树，如：AVL树（Adelson-Velskii和Landis，1962）、重量平衡树（Nievergelt和Reingold，1973）、红黑树（Guibas和Sedgewick，1978）和Treaps（Cecilia和Raimund，1989）等。在所有类型的高度平衡搜索树中，平衡信息都保存在每个节点中，并且在每次插入或删除之后通过沿着访问路径（从根到插入或删除项的路径）执行一系列变换（旋转）来进行重新平衡。红黑树中的变换由于我们需要使用这些树作为实现包含动态变化的优先级队列的数据结构，因此树的转换成本将影响我们实现的效率，而红黑树具有高效的转换。因此，根据我们的要求，红黑树是合适的表示。3.2.2. 操作定义为了实现追溯优先级队列，我们需要有一种方法来维护所有元素的生存期以及元素本身。因此，为了实现这样的功能，我们维护了两棵红黑树：T ins和T d_m，它们维护了集合Insert和Del_Min。Set Insert维护密钥对其中x表示项，t表示项x的插入时间。此外，setDel_Min还维护执行del_- min操作的时间。树Td_m按时间排序。 另一棵树Tins由项目值索引，第二次索引是根据时间，即（k1，t1）（k2，t2）当且仅当（k1 k2）或（（k1 = k2）^（t1 t2））。这两棵树之间有联系，●●●●●Sunita，D. Garg/沙特国王大学学报-计算机与信息科学33（2021）364-373367节点，因为树Td_m的每个节点与Tins的节点链接，其键是该del_min操 作 的 返 回 值 在 类 似 的 行 上 ， 如 果 Tins 的 每 个 节 点 是 Revoke（Del_Min（t））操作的结果，则该节点与其对应的del_min链接。每当del_min操作被执行时，要从树Tins中删除的节点实际上并没有被删除，而是被标记为无效，因为我们还需要维护过去的信息稍后，如果del_min被撤销，则该节点再次被标记为有效节点。除了上述操作之外，追溯优先级队列还需要识别返回值受到影响作为伪代码的所有上述操作的定义以及树Tins和Td_m的定义已经用示例表示如下：图2表示在我们开始对这两个树应用追溯更新之前这两个树的配置。i) 插入（x，t））在时间t根据其优先级值执行键（x，t）到树Tins中的插入在树中的插入按以下步骤完成：(i) 如果t是当前时间意味着在时间t之后没有执行del_min，则根据键值搜索树，然后根据时间找到要插入的键的位置。在搜索终止的地方，附加一个包含新键（x，t）的新节点。(ii) 否则，在树Td_m中找到在时间t之后被删除的最小值，比如k，并将其作为第一个不一致的操作返回，同时在时间t将x插入优先级队列。图3示出了对图1的树应用操作Pocke_Insert（7，11）的效果。二、Replike_Insert（x，t））Insert（Tins，x，t）;//在时间t处将x插入高度平衡树TinsP = Search_Min（Td_m，t）;//在树Td_m中搜索在时间t之后删除的最小键值。如果（P！ = NULL）return（P）;//返回第一个不一致的操作。其他return（NULL）;ii) 最小化_Del_min（t））在时间t执行从优先级队列中要执行删除，我们必须检查在此之前执行的删除最小操作。执行del_min的步骤如下：图二. 树T ins和T d_m。图三. 在优先级队列中，树Tins和Td_mi) 如果del_min要在最近的时间执行，那么只需从Tins中找到最小键值，并将其从Tins中删除，然后将其插入Td_m中。ii) 否则，从树Td_m中找到在给定时间t之前立即删除的键值k现在从树Tins中找到大于密钥k '的最小密钥kk是del_min操作的结果。图4示出了当对图3中的树应用Delke_Del_- Min（8）操作时它们如何改变。最小值（t））P = Search（Td_m，t0）;//其中t0 = max（t00eTd_m and t00 t）if（P = ∞）//在时间t之前没有执行del_min N = Find_min（Tins）;Return（N）;elseK0 = P.数据;//其中k搜索（Tins，k）//其中k = min（k00eTins且 k00> k0）见图4。 在优先级队列中，树Tins和Td_m368Sunita，D. Garg/Journal of King Saud University- Computer and Information Sciences 33（2021）364- 373iii) Revoke_Insert（t））撤消在时间t执行的插入操作。要做到这一点，请检查在时间t之后是否执行了任何del_min操作。i) 如果是，则返回时间t之后执行的第一个del_min作为不一致操作。ii) 否则，将在时间t插入的节点设为无效，并查找iv) Revoke_Del_Min（t））撤消在时间t执行的删除操作。这相当于将在时间t删除的项再次插入优先级队列。图6显示了影响在图5上应用操作Revoke_Del_Min（8）。树T中对应于时间t的条目，并标记该条目无效。图5显示了当Revoke_Insert(4)操作适用于它们。撤销（插入（t））P = Search_Min（Td_m，t）;//在树Td_m中搜索在时间t之后删除的最小键值。如果（P！= NULL）return（P）;//返回第一个不一致的操作其他P = Search（Tins，t）; P.Valid =False;撤销（Del_Min（t））P = Search_Min（Td_m，t）;//在树Td_m中搜索在时间t之后删除的最小键值。如果（P！ = NULL）return（P）;//返回第一个不一致的操作。其他Insert（Tins，x，t）;//在时间t插入x到高度平衡树Tins中v) Find_min（t）：返回时间t时优先级队列中存在的最小元素。如果t是最近的时间，在此之后没有del_min被执行，则简单地在对应于时间t的树Tins中执行搜索操作，否则从在给定时间t之前已经从优先级队列中删除的树T d_m中找到最大键值（例如k即，K“是时间t时优先级队列中的最小值图7给出了表示在应用操作Find_Min（13）之后的优先级队列的最终树。Find_min（t）P = Search_Min（Td_m，t）;//在树Tdm中搜索在时间t删除的最小键值if（P = NULL）Q = Search_Min（Tins，t）;//在时间treturn（Q.val）;其他return（P.val）;图五. 在优先级队列中进行Revoke_Insert（4）操作后生成树Ts和Td_m见图6。 在优先级队列中进行Revoke_Del_Min（8）操作后生成树Tins和Td_m见图7。 优先级队列中Find_Min（13）操作后的树Ts和Td_m1Sunita，D. Garg/沙特国王大学学报-计算机与信息科学33（2021）364-3733693.3. 建议算法：使用追溯优先级队列的动态Dijkstra该算法是对标准Dijk-stra优先级队列相应地适应该变化，并返回操作序列中由于边权重的变化而受到影响的第一个操作3.3.1. 算法：动态Dijkstra（D_Dij）在动态Dijkstra算法中，我们首先检查更新操作是否影响到目前为止执行的操作所提出的算法的步骤如下所述：步骤1：检查更新的边的头顶点是否在追溯优先级队列（RPQ）中。步骤2：如果它不在RPQ中（意味着没有先前计算的路径将受到此更改的影响），则转到步骤6。步骤3：否则，如果与更新的边的头顶点相对应的条目是RPQ中的活动条目（该顶点未在任何现有最短路径中使用），则转到步骤4，否则转到步骤5。如果松弛插入（Tins，t.val）16：插入返回在追溯优先级队列中实现的下一个操作，比如节点m。返回第11步17：如果结束18：结束19：如果结束20：如果结束21：如果3.3.2. 例如使用图的图形。 9，我们展示了当允许边的边权重改变（即增加和减少）时，我们的算法所执行的操作。下面的每一行表示在时间t的优先级队列的状态，即，优先级队列中的每个条目是在该特定时间的队列中的有效条目队列中的每个条目是一个三元组（v，val，pred），其中v表示顶点，val表示该顶点与源顶点的预测距离，pred给出该顶点在预测最短路径上的前导。时间优先级_队列步骤4：如果更新是负（即：重量的边缘已经减少），然后更新更新后的边的尾顶点的距离并转到步骤1，否则转到步骤6。步骤5：否则在边缘被删除之前立即在优先级队列中移动，并根据需要容纳改变。转到步骤1。步骤6：退出此外，通过流程图（图8）以及伪代码详细描述这些步骤动态Dijkstra（D_Dij）//边e的权重改变了a（增加）或-a（减少）1：N = Search（Tins，eh）;// eh表示边e 2的头顶点：如果（N ==NULL）则3：退出//最短路径不变，正常进行4：else如果N是优先级队列中的活动条目，则// N尚未删除5：如果pred[eh] == et，则6：更新优先级队列中的顶点et的估计距离（d[et]）7：其他在优先级队列中移动到eh被删除的时间之前，比如节点m。9：如果（pred（eh）== et），则t = 0 0，0，无t = 1 A，2，O C，4，O B，5，Ot = 2C、4、OB、4、AD、9、AF、14、At = 3B、4、AE、8、CD、9、AF、14、At = 4 E，7，B D，8，B F，14，A在时间t = 5处，边缘BD的权重增加到5。由于顶点D仍然在优先级队列中，这意味着边BD到目前为止还没有被包括在任何最短路径中。因此，将顶点D的估计距离增加1并正常进行10：更新顶点et的估计距离（d[et]）在优先队列中。11：优先级队列返回由该改变（比如节点n）实现的del-min/<$放松节点n（n.v）顶点的向外边。/12：foreache13：如果（pred [e14：d[e15：放松边缘et = 5 E，7，B D，9，B F，14，A或者假设，在时间t = 5处，边缘BD的权重减小到1。由于顶点D仍然在优先级队列中，这意味着边BD到目前为止还没有被包括在任何最短路径中。因此，将顶点D的估计距离更新3并正常进行370Sunita，D. Garg/Journal of King Saud University- Computer and Information Sciences 33（2021）364- 373见图8。动态Dijkstra（D_Dij）流程图。图9.第九条。动态Dijkstra算法的示例图t = 5 E，7，B D，5，B F，14，A在时间t = 7处，边缘OB的权重增加到7。由于顶点B先前已在优先级队列中，因此我们需要遵循其中已使用边OB的路径，以便可以相应地更新它们。- 在顶点B的删除之前的时刻，即在时刻3，在优先级队列中移动。我们不需要改变B的最短路径的值，因为它小于包括边OB的改变的权重的新的值。因此，在这种情况下，最短路径也不会改变，我们正常进行。t = 8 T，13，D F，14，A在时间t = 9处，边AB的权重减小到1。由于顶点B先前已在优先级队列中，因此移入优先级队列在紧接删除ver之前的时间t = 6 D，9，B F，14，AT，14，Etex B，即在时间3B在该点的前序是A，因此其最短路径为3。追溯优先级队列中的值具有~Sunita，D. Garg/沙特国王大学学报-计算机与信息科学33（2021）364-373371改变，它将自动重新排列自己，并返回受此改变影响的操作。此时，优先级队列可以表示为：表1实验数据集：随机图。图顶点数|v|边数|E|电话：+86-21 - 5599999t = 10 E，6，B D，7，B T，13，D F，14，A下一个有效的操作是针对顶点E。现在对E执行del_min。表2实验数据集：美国公路网。下一个有效的操作是针对顶点D。对D执行del_minDijkstra应该恢复，因为所有更改都已完全传播。在下一节中，所提出的算法进行了实证分析和比较结果。4. 实证分析通过与两种实际有效算法的比较，进行了实证分析.在这里，我们的动 态 Dijkstra （ D_Dij ） 算 法 的 性 能 已 经 与 Ramalingam 等 人（Ramalingam和Reps，1996年; Ramalingam和Reps，1996年）和Demetrescu等人（Demetrescu和Italiano，2003年）给出的算法进行了比较。已知Ramalingam等人的算法在实践中非常快（Fortz和Thorup，2000; Frigioni等人，1998，2000），它通过识别其与源S的距离受更新影响的顶点子集来工作。然后通过在这些节点上运行Dijkstra算法来更新距离。Demetrescu等人的算法利用Dijkstra类算法中的均匀路径思想，减少了总的边缘扫描次数，克服了性能瓶颈。我们还 比 较 了 我 们 提 出 的 算 法 与 Burlington 等 人 给 出 的 堆 减 少 技 术（Burlington等人，2003）应用于Ramalingam等人（Ramalingam和Reps，1996）和Demetrescu等人（Demetrescu和Italiano，2003）的算法。实验是在2.30 GHz Intel Pentium III处理器和2 GB RAM的计算机上进行的。使用C语言（使用-O3优化选项使用gcc-4.8.2编译）执行或模拟。使用系统函数测量CPU时间，并使用工具Valgrind进行内存分析。在我们的实验中，我们考虑了两种类型的图。一个是随机图数据集，如表1所述。生成n个节点、m条边和随机整数边权的随机图。更新序列也是通过选择任意边上的任意更新操作随机生成的另一个图形数据集取自实验包（http：//www.dis.uniroma1.it/demetres/experim/dsp/（ 最后一次访问于2018年1月15日）由Demetrescu等人提供。（Demetrescu和Italiano，2006年）。用于实验的图形数据在软件包中以XML文件的形式提供，该文件对应于真实世界的美国道路网络数据（ftp://edcftp.cr.usgs.gov（最后一次访问时间为2018年1月15日））。表2描述了用于实验的数据包中的美国道路网络图的详细信息。此外，所提出的动态Dijkstra-（D-Dij）算法的性能已经与算法D_Rr （ 由 Ramalingam 等 人 给 出 （ Ramalingam 和 Reps ， 1996;Ramalingam和Reps，1996））、D_Up（由Demetrescu等人给出（Demetrescu和Italiano，2003））和D_Rr_B &D_Up_B（基于由Burlington等人给出的堆缩减技术（Burlington等人，2003年）。通过在两种不同类型的图上对这五种算法进行实验所得到的比较结果已通过图1和图2示出。 10-15随机图和美国道路网络图的实验表明，D_Dij具有性能图。图10和14中所示的稀疏图，与依赖于输入图拓扑的D_Rr的稀疏图相比。此外，内存使用图。图11和15所示的算法D_Dij的动态更新比所有其他算法都要小，因为所提出的算法不使用任何额外的信息来执行动态更新。但D_Rr保持额外的信息，如受影响的顶点的子集和D_Up还保持执行动态更新的统一路径。通过使用堆减少技术减少了内存使用，从而减少了D_Rr_B和D_Up_B的内存需求。从图10的结果可以看出，所提出的算法D_Dij的性能优于其他两种算法，并且由于D_Rr和D_Up算法中的开销增加，算法D_Rr和D_Up所花费的时间也随着底层图大小（边的数量）的增加而增加。此外，图13示出了在D_Rr的情况下的存储器使用不受图大小的太大影响，但是在D_Up的情况下，存储器使用随着边的数量的增加而显著增加。对于所提出的算法D_Dij，内存使用不会随着图的边数的增加而R_G1100500t = 3B、3、AE、8、CD、9、AF、14、AR_G22501250R_G33251625R_G45152575R_G56253125因此，将使用新的距离值再次执行del_min forR_G67353675对于顶点B。R_G78004000R_G88854425t = 11D、7、BT、13、DF、14、A图XML文件数量的顶点|v|边数|E|图-1RI.xml170490t = 12T、12、DF、14、A图-6MI.xml6952162图7MO.xml8092510图-8CA.xml9452768现在，我们可以在这一点上，正常执行图9FL.xml13683892图3SD.xml3961132图4MD.xml4901390图5IN.xml5991890372Sunita，D. Garg/Journal of King Saud University- Computer and Information Sciences 33（2021）364- 373见图10。随机图的D_Up、D_Rr、D_Up_B、D_Rr_B和D_Dij所用的比较时间。见图11。比较随机图的D_Up、D_Rr、D_Up_B、D_Rr_B和D_Dij的内存使用情况。见图12。D_Up、D_Rr和D_Dij对不同数量的边所花费的比较时间。图13岁比较D_Up、D_Rr和D_Dij对不同边数的内存使用情况见图14。比较美国道路网络数据的D_Up、D_Rr、D_Up_B、D_Rr_B和D_Dij所用的时间。5. 结论我们提出了使用回溯数据结构paradigm表示的时间线需要与动态最短路径问题中的每个操作我们的方法图15.比较美国道路网络数据的D_Up、D_Rr、D_Up_B、D_Rr_B和D_Dij的内存使用情况。为动态最短路径问题提供了有效的解决方案。由于我们使用高度平衡的搜索树来实现追溯优先级队列，因此所有操作Sunita，D. Garg/沙特国王大学学报-计算机与信息科学33（2021）364-373373优先级队列的长度取决于底层树数据结构的高度此外，在图中动态变化的情况下，计算的数量较少，因为我们在时间上在更新下的边将被用于任何最短路径的时间之前的点处向后移动。我们选择性地选择实际受到变化影响的点，并仅对该部分应用更新。使用回溯数据结构的最短路径问题的解决方案可以很容易地适应放松我们在工作中所做的假设。变换（重新加权）可以应用于适应我们的解决方案的情况下，一般的图形（图形与积极或消极的边缘权重）。此外，我们的动态Dijkstra算法可以用来解决动态全对最短路问题。该解决方案的性能可能略低于迄今为止已知的最佳资源界限。此外，提高底层追溯优先级队列的效率可以进一步提高该方法的性能。将来，我们将计划将多个更新操作作为一个操作来处理，这可能会进一步减少问题的时间范围引用美国阿卡尔Blelloch，GE，Tangwongsan，K.，2007.非遗忘回溯数据结构。技术报告CMU-CS-07-169。Adelson-Velskii，G.，兰迪斯，E.M.，1962.组织信息的算法。苏联数学，女博士3，1259-1263.Bergamini，E.，Meyerhenke，H.，2015年。介数中心性的全动态近似在欧洲算法研讨会上的程序pp。155- 166页。Bergamini，E.，Meyerhenke，H.，Staudt，C.，2015.大型演化网络中的介数中心性近似。在：会议程序的算法工程实验pp。133-146。Bernstein，A.，2013.加权有向图中删除情形下的最短路径维护。STOC，725-734。Bernstein，A.，罗迪蒂湖2011.删除情形下维护近似最短路径的改进动态算法。在：程序的ACM-SIAM研讨会离散算法pp。公元1355-1365年。南卡罗来纳州伯灵顿，缓刑，MG，Thorup M.，2003.加速动态最短路径算法。AT T实验室研究，TR TD-5 RJ 8B。Cecilia，R.A.，Raimund，G.S.，1989.随机搜索树。在：计算机科学的基础程序。Dahshan，M.，2013.光交换网络中采用双网拓扑的最短节点不相交路径。Int. 阿拉伯河告知。Technol. 10（4），365-372.Demaine，E. D.，Iacono，J.，Langerman，S.，2007.追溯数据结构。ACMTrans.Algorith. 3（2），13.Demetrescu，C.，Italiano，G.F.、2003年。一种新的动态全对最短路径算法在：第35届年度ACM计算理论研讨会（STOC'03），圣地亚哥，加利福尼亚州，pp。159-166。Demetrescu，C.，意大利语，G.F.，2006.动态全对最短路径算法的实验分析。ACMTrans.算法 2（4），578-601。Dijkstra，E.W.，一九五九年关于图中两个问题的注记 J. Numeris。数学1，269甚至，S.， Shiloach，Y.， 1981. 一个在线边删除问题。 J. ACM 28（1），1-4。Fortz，B.，Thorup，M.，两千通过优化OSPF权重的互联网流量工程在：IEEE计算机通信会议的程序pp.519-528.Frigioni，D.，Ioffreda，M.，南尼，美国，Pasqualone，G.，1998. 单源最短路径问题的动态算法分析。ACM J.Exp. 算法3.Frigioni，D.，Marchetti-Spaccamela，A.，南尼，美国，2000.维护最短路径树的全动态算法。J. Algorith。34（2），251-281。ftp://edcftp.cr.usgs.gov（2018年1月15日访问）。F