改进的几乎无圈图的最短路算法及其时间复杂度分析

232理论计算机科学电子笔记42（2001）网址：http://www.elsevier.nl/locate/entcs/volume42.html17页改进的几乎无圈图Shane Saunders1高冈忠雄2新西兰基督城坎特伯雷大学计算机科学系摘要Dijkstra这里n是顶点数，m是图中的边数。如果图是近无环的，其他算法可以实现低于Dijkstra算法的时间复杂度。Abuaiadh和Kingston给出了一个近似无环图的单源最短路径算法，其时间复杂度为O（m+nlogt），其中新参数t是在优先级队列操作中执行的delete-min操作的数量。 如果图是近无环的，那么t应该很小，并且算法优于Dijkstra算法。Takaoka，使用不同的定义为非循环，给出了一个算法，O（m+1）nlogk）时间复杂度。在该算法中，新参数k是图中强连通分量本文提出了两个新的近似无圈图的最短路算法。第一个是一个广义的单源（GSS）算法的近无环图，它的时间复杂度为O（m+rlogr），其中r是触发顶点的数量，与触发顶点定义为树根的结果时，图 分解成树。第二个是一个新的几乎无环图的全对算法，具有O（mn+nr2）的最坏情况下的时间复杂度，其中r是预先计算的反馈顶点集的顶点数的几乎无环图。对于某些图，这些新算法的时间复杂度比以前的算法有所改进。将新的GSS算法应用到Takaoka算法中1介绍Dijkstra1电邮地址：sas59@cosc.canterbury.ac.nz2电邮地址：tad@cosc.canterbury.ac.nz2001年由ElsevierS cienceB. V. 操作访问和C CB Y-NC-ND许可证。桑德斯和赤冈233如果使用斐波那契堆[3]作为边界集数据结构，则为case time。 这里n是有向图中的顶点数，m是有向图中的边数。Dijkstra算法的变化和改进，已经看到al-出租更适合某些类别的图。这些新算法通过引入一个与图结构相关的参数来提高算法的时间复杂度。一类这样的算法对几乎无圈图有更好的改进。Abuaiadh和Kingston [1]给出了近似无圈图的单源最短路径算法，其时间复杂度为O（m+nlogt），其中新参数t是在优先级队列操作中执行的delete-min操作的次数。如果图是近无环的，那么t应该很小，并且算法优于Dijkstra算法。对于这个算法，t的定义与图的结构没有直接关系。Takaoka [4]使用不同的非循环定义，给出了一个时间复杂度为O（m+nlogk在该算法中，新参数k是图中强连通分量的最大基数。k的定义与图的结构直接相关。Takaoka还给出了这种新算法的混合形式，它将新方法与Abuaiadh和Kingston的方法相这些改进的算法表明，对于几乎无环图，在优先级队列操作中执行的delete-min操作的数量可以减少。使用Dijkstra相比之下，单源最短路径问题的有向无环图与积极的边缘权重涉及没有删除最小操作，允许总的时间复杂度为O（m+n）。delete-min操作在时间复杂度中引入了一个额外的因素，这会增加算法的运行时间如果图的结构允许删除min操作的数量减少，则改进的算法具有更好的时间复杂度。这些改进算法从图的结构和时间复杂度两个方面对如何更有效地计算最短路径问题有了更好的理解本文提出了两个新的近似无圈图的最短路算法。第四节提出了一个新的广义单源（GSS）最短路算法，其时间复杂度为O（m+rlogr），其中r是触发顶点的个数。触发顶点是当图被分解成树时产生的树的根。第5节然后一般化的选择触发顶点到任何反馈顶点集，其中一个新的全对最短路径算法的最坏情况下的时间复杂度为O（mn+nr2）是可能的。 对于许多近无环图，r远小于n，允许这种新的全对算法执行O（mn）的时间复杂度。为了介绍这些新算法，第2节首先描述了Dijkstra算法，然后概述了现有的最短路径算法的近无环图。第3节描述了现有GSS算法的改进总结发言桑德斯和赤冈234--在第6节中给出。2现有最短路径算法本节首先描述DijkstraDijkstra在图中，E是边的集合。 这里V由整数1，2，.，n. 在Dijkstra算法的以下描述中成本函数c（v，w）给出从顶点v到顶点w的边成本。Dijkstra集合S存储已经计算出最短距离的顶点。集合F包含顶点v，这些顶点具有相关联的十维最短路径距离d[v]，但不具有最终最短路径距离。这个试探距离是只包含v和S中顶点的最短路径的距离。F中的任何顶点都直接连接到S中的某个顶点。我们假设图中的所有顶点都是从源顶点s可达的。算法1Dijkstra{s};F=0;对于OUT（s）中的每个w，执行{将w加到F，其中d[w] =c（s，w）;}whileFis not emptydo{选择v，使得d[v]在F中的v中最小;从F中删除v;/* 删除min */把v加到S上;对于OUT（v）中的每个w，而不是S中的do{如果w不在F中，则{d[w]=d[v]+c（v，w）;将w添加到F;/* insert */}否则{d[w]=min（d[w]，d[v]+c（v，w））;/* 减小键 */}}}在F上有三种操作：插入、删除min和减少键。桑德斯和赤冈235/∞斐波那契堆[3]、2-3堆[5]和三项式堆[6]支持插入在O（logn）时间内删除min因为每个顶点都被访问过，所以有n个插入和n个删除min操作。 减少键操作的数量是O（m），因为这对应于图中的边的数量。因此，当使用斐波那契堆、2-3堆或三项式堆时，F的总体时间复杂度为O（m+nlogn）。单源最短路径问题的时间复杂度可以针对特定的图类型来降低。如果图是无环的，最短路径问题只需要O（m+n）时间来解决。Abuaiadh和Kingston [1]改进了Dijkstra由S外部的边所指向的顶点称为“双顶点”。如果F中的一个顶点是一个容易的顶点，它从F中被删除。当F中没有容易顶点时，需要删除min操作如果需要t个这样的删除min操作，则算法在边界集合上总共执行n个插入、t个查找min和n个删除由于这些堆操作和使用修改的Fibonacci堆作为边界集数据结构，算法对于一个给定的图，如果t的值比n小，Abuaiadh和KingstonTakaoka [4]基于图的强连通（SC）分支给出了几乎无圈有向图的单源最短路算法。在Takaoka的算法中，一个图被分解成SC组件和连接它们的非循环结构。这需要使用Tarjan算法[7]对图进行初始扫描，以确定强连接分量。最短路径计算通过连接SC组件的非循环结构高效地进行。使用广义单源（GSS）最短路径算法计算SC组件内的最短路径。如果最大强连通分支的顶点数为k，则Takaoka 对于给定的图，如果k的值小于n，则TakaokaTakaoka指出，这种新算法可以与Abuaiadh和Kingston的算法相结合，成为一种混合算法，它结合了每一种算法的优点。广义单源（GSS）最短路径问题，定义为Takaoka [4]指定了图中每个顶点v的初始距离d0[v]。GSS问题的算法与Dijkstra算法相同，除了它从边界集中的所有顶点开始。3为此，给定SC分量的GSS初始距离由通过非循环结构到SC分量的最短路径产生。下面给出了Takaoka [4]的GSS算法，但与Dijkstra的算法类似，以进行比较。此外，最初仅将初始距离非无限的顶点放置在3这不是严格必要的，因为只有d0[v]=的顶点最初需要在边界集中。因此，如果只有一些顶点具有非无限初始距离，则可以避免大的边界集。桑德斯和赤冈236边境设置。算法2GSS算法S=0;F=0;对于V中的每个v，do{如果d[v]/=∞，则将v加到F，其中d[v] =d0[v];}whileFis not emptydo{选择v，使得d[v]在F中的v中最小;从F中删除v;/* 删除min */把v加到S上;对于OUT（v）中的每个w，而不是S中的do{如果w不在F中，则{d[w]=d[v]+c（v，w）;将w添加到F;/* insert */}否则{d[w]=min（d[w]，d[v]+c（v，w））;/* 减小键 */}}}GSS的使用不仅限于Takaoka的算法几乎无环图。传统的单源最短路问题具有d0[s] = 0和d0[v]=∞，因此所有的最短路都必须从顶点出发S.如果我们有其他的源顶点u，其中d0[u] = 0，则得到的最短路径距离d[v]将是从最近的源到v的最短路径。3GSS算法由Takaoka [4]描述的混合算法使用Abuaiadh和Kingston第4节中介绍的新GSS算法改进了现有的GSS算法，因此更广泛的近似无环图可以从改进的时间复杂度中受益。这是通过引入与图结构相关的新参数r来完成的。这是一个复杂的问题，时间复杂度为O（m+rlogr）。Abuaiadh和Kingston的方法不能保证比Dijk-stra算法改进的时间复杂度的几乎无环图结构是可能的。对于相同的图，新算法可以保证时间复杂度的改善。考虑解决一个最短路径问题，其中整个图是强连通的。这样，Takaoka算法的时间复杂度就不能比Dijkstra算法的时间复杂度提高.类似地，如果一个图（或GSS的SC组件）没有产生任何容易的顶点，则可以桑德斯和赤冈237≤在运行Abuaiadh和Kingston的算法时，时间复杂度没有改善考虑使用Abuaiadh 和Kingston 的方法来解决某些图或SC 组件上的GSS 问题。Abuaiadh和Kingston算法的时间复杂考虑图的一部分中的顶点链结构，定义如下：• 链由顶点v0，v1，.，v j.• 链中的边的形式为（v i，v i+1），其中i= 0，1，.，j− 1。• 顶点v1，v2，. . . vj只有一个输入边。• 假设对于GSS问题，链上每个顶点的某个任意初始距离。现在考虑如果当使用Abuaiadh和Kingston的方法计算GSS问题时，由于删除min操作，该顶点链上的顶点vi被移动到解集会发生什么。 在此删除min所有顶点之后，对于i< k j的v k将随后被移动到解集，因为每个都变得“容易”。在此过程中，通过减少键操作，从链上的一个顶点到下一个顶点的暂定距离被更新。如果存在初始距离分布，使得删除min操作以v j，vj-1，.的顺序从F中移除顶点，则会发生最坏情况，v0. 在这种情况下，链上没有顶点变得容易，并且如果使用Dijkstra算法，则会发生j删除min操作。在最好的情况下，一个删除min操作将从F中删除顶点v0（链上的头顶点），随后的删除操作将从F中删除链上所有剩余的顶点。 如果可以将删除min操作限制在图中链的头顶点，则可以降低最坏情况下的时间复杂度。4几乎无圈图的改进GSS算法本节介绍了一个新的GSS算法几乎无圈有向图。对于某些图类，该算法改进了Abuaiadh和Kingston的算法[1]（用于求解GSS问题时），并介绍了对Takaoka算法[4]的改进。给出了新算法的基本形式新算法的更复杂的变体（未给出）可以将时间效率提高一个常数因子。第三节使用顶点链来介绍改进Abuaiadh和Kingston方法在GSS问题中的时间复杂度同样的概念可以从顶点链推广到顶点树定义IN（v）为顶点u的集合，使得图中存在边（u，v）。然后，图中的树结构可以识别如下：• 树结构中的根顶点v具有|IN（v）|> 1.桑德斯和赤冈238||• 树结构中的非根顶点v具有|IN（v）|= 1。用tree（v）表示以顶点v为 如果是从树T中的顶点到某个树的根顶点w的有向边，则T是w的邻树。假设在图中的树结构树（v）的根顶点v上发生删除min操作。 然后，树（v）中的所有其他顶点将随后移动到S，因为每个顶点变得容易。顶点向S的移动传播通过整个树结构。这是Abuaiadh和Kingston方法的最佳案例。然而，在大小为j的树中，Abuaiadh和Kingston的方法的最坏情况图1示出了被视为一组树结构的图。指向根顶点的边显示为虚线。在简化视图中，具有相同源树和目标根顶点的此类边使用单个伪边表示。从简化的角度来看，很容易看出，一般来说，每个树结构只需要一次删除min操作的Fig. 1. 图的例子被看作是链接的树结构。新算法的第一步是扫描图中的每个顶点v，以根据IN（v）的值确定根顶点和非根顶点。 在本说明书中，根顶点被称为“触发”顶点。触发顶点触发树中其他顶点的最短路径距离更新。请注意，此算法假设图中的所有非触发顶点都是某个树根的后代。如果GSS问题是在强连通图或某个图的SC分量上，则总是这种情况。4因为4对于特殊情况，强连通图是顶点环，使得每个顶点v都具有IN（v）=1，可以随机选择任何一个顶点作为触发器。桑德斯和赤冈239||对于一个非强连通的图，如果存在非触发器不是某个根顶点的后代，则可以很容易地通过确定顶点v使IN（v）= 0来改变算法。该算法的其余部分包括两个更新通过图。算法3给出了算法的第一次更新过程。这计算了每个树中顶点的第一个试探性最短路径距离d1[v]。在第一次更新过程中不执行删除最小值操作。在算法开始时，每个顶点v都有一个GSS初始距离d0[v]。树中顶点的更新需要维护队列Q。 如果队列保持先进先出，那么树中的顶点将在广度优先搜索中更新。 如果队列保持后进先出，那么树中的顶点将在深度优先搜索中更新。注意，如果使用深度优先搜索，算法的这一部分可以递归实现，从而消除了算法维护队列的需要算法3新GSS算法的第一阶段/* 假设触发顶点已知 */Q=0;对于每个顶点v，d1[v] =d0[v];对于每个触发顶点udo{将OUT（u）中的非触发顶点添加到Q;当Qdo{从Q中移除v;对于OUT（v）中的每个顶点w，do{d1[w] =min（d1[w]，d1[v]+c（v，w））;如果w不是触发顶点，则将w加到Q;}}}算法3中的距离更新被限制在树之间传播。尽管这不是算法工作的严格必要条件，但现在它使解释变得更简单。该算法的一个更有效的版本（未给出）允许距离更新不太受限，这可以减少第二次更新过程中的距离更新次数。第一试探性最短路径距离d1[v]是由初始距离d0[v]或以下形式的路径产生的最短距离：（v1，v2，.，v k，v），k≥ 1其中：d1 [v] = d0 [v1]+ c（v1，v2）+. +c（vk，v）路径长度定义为桑德斯和赤冈240∅≤≤路径，该路径的长度为k。这样一条长度为k的路径的性质是：• 每个vi（1≤i≤k）都位于同一棵树T上;也就是说，对于1≤i≤k，vi <$T。• 如果顶点v是非触发器，则它与顶点vi（1≤i≤k）。• 若顶点v是触发点，则顶点vi（1i k）在v的邻树上.注意，在这个限制算法中，没有触发顶点会被包含在另一个触发顶点的第一个试探性最短路径中。触发顶点只能从与相邻树中的非触发顶点一样远的地方更新在第一次更新结束时，以下断言成立：• 对于每个触发顶点u，已经计算了可以由u的相邻树中的非触发顶点产生的到u的最短路径。这个距离以d1[u]给出。• 对任何触发顶点u的d1[u]的任何改进都必须涉及到来自另一个触发顶点的路径。算法4给出了第二更新遍算法。算法4新GSS算法的第二阶段（从A1-出租3继续）1.S=;2.将所有触发顶点插入F;3.对于每个顶点v，d[v] =d1[v];4.whileFis not emptydo{5.选择u使得d[u]是F中u中的最小值;/* 删除min */6.从F中移除U;7.把u加到S;8.把u加到Q;9.当Qdo{10.从Q中移除v;11.对于OUT（v）中的每个顶点w，do{12.d[w] =min（d[w]，d[v]+c（v，w））;/* 如果w是一个触发顶点，则可能会发生减少键操作* */13.如果w不是触发顶点，则将w加到Q;14.}15.}16. 个文件夹对于第二次更新，只有触发顶点涉及边界集F和解集S。在第5行和第6行，选择具有最小d[u]的触发顶点u，并从F中移除。称之为最小触发顶点。然后将该顶点添加到解集S。桑德斯和赤冈241≤ ≤ −在第5行的第i次迭代之前，令解集S的状态为：S ={u1，u2，...， u i−1}（按此顺序添加）然后我们有以下定理：定理4.1(i) 对于触发顶点uk <$S（1 ≤ k ≤ i − 1），d [uk]是到顶点uk的最短距离。(ii) 对于所有顶点v ∈ tree（uk）和所有uk（1 k i 1），d [v]是到顶点v的最短距离。(iii) 对于触发器顶点u <$F，d [u]是到u的最短路径的距离，该最短路径仅允许通过非触发器、S中的触发器顶点和u。归纳法（Induction）基础i= 1：上面的断言1和2自动为真，因为对于i= 1，S为空。对于上面的断言3，d[u]是由算法3正确计算的，因为S是空的。诱导步骤。假设定理对于S ={u1，u1，...，u i−1}。 如果ui是F中触发顶点中的最小值，则d[ui]是到ui的最短距离，因为通过F中任何其他触发顶点的路径的距离将更长。此外，对于v树（ui），最短距离d[v]被正确地计算，因为没有经过其他触发器的到v的更短路径最后，对于F中剩余的触发顶点u，如果tree（ui）是u的相邻树，则d[u]将被更新。因此，对于F中剩余的触发器u，通过u1，u2，.中的触发器顶点的最短路径的距离， Ui被正确地计算，因为Ui和树（Ui）将是要经过以到达Ui的最新可能的触发器和树结构。因此，定理对于S={u1，u2，.， u i}。✷设图中共有n个顶点和m条边。时间复杂度为O（m）。现在假设一个斐波那契堆用于F。假设图中有r个触发顶点，那么在第二次更新中将有r个删除min操作，每个操作最多花费O（log r）时间，给出组合的最坏情况时间复杂度O（r log r）。第二次更新也有一个O（m）的时间组件，它考虑了遍历的每条边和任何减少键操作。最坏情况下整个算法的时间复杂度为O（m+rlogr）。对于传统的单源问题，除了源顶点之外，所有初始距离都是无限的。这允许当源顶点是非触发器时的简化的第一更新通道，并且当源顶点是触发器时没有第一更新通道。时间复杂度为O（m+rlogr），时间复杂度为O（m + r log r）。Abuaiadh和Kingston算法的时间复杂度为O（m + n log t），取决于删除min操作的次数t。对于GSS，t的最坏情况值是O（n），但桑德斯和赤冈242对于传统的单源问题，t的最坏情况值仅为O（r）。对于传统的单源问题，Abuaiadh和Kingston的方法可能的改进新算法所带来的改进量在很大程度上取决于图的结构，因为这决定了r的值，t.对于一个由r个树结构组成的强连通图，如果t是O（n），那么Abuaiadh和Kingston在相同条件下，新算法的时间复杂度为rn，最坏情况时间为O（m+rlogr）.虽然最坏情况下的时间复杂度有所改善，但在特殊情况下，Abuaiadh和Kingston算法的运行可能会更好。这将发生在当删除最小发生在少数触发顶点，这反过来又导致所有其余的触发顶点最终成为容易顶点。目前，重要的结果是，该算法的最坏情况下的时间复杂度保证是一样好或更好的比Abuaiadh和金士顿的算法GSS。这种新的GSS算法是对Takaoka单源无圈图算法的进一步改进，它以混合的形式使用它们。另一个改进是采用Abuaiadh和Kingston的“简单”顶点的概念，并将其扩展到“简单”触发顶点。然后可以在O（1）时间内从F中识别并删除容易触发的顶点，从而减少所需的删除min操作如前所述，在新算法中，对最短路径距离的更新是有意限制的，以使描述更简单。该算法的改进版本可以允许距离更新在第一次更新过程中在相邻顶点之间传播，而不会改变算法的正确性。然后，如果在第二次更新过程中，到顶点的距离v没有更新，则算法不需要继续更新超过v的距离。 通过在不更新的顶点处终止搜索，平均而言，时间效率可能会略有增加，即使最坏情况下的时间复杂度不会改变。进一步的工作可能改进这个算法包括一般化，从树分解到一个特殊形式的非循环分解。对于由图的分解产生的非循环部分A，A中的顶点必须只有一个触发顶点祖先u。因此，现在触发顶点u触发更新到其非循环部分而不是树结构。这使得触发顶点的选择限制较少，从而减少了触发顶点的数量和必须发生的删除最小值5一种改进的全对算法上一节介绍的GSS算法根据图中的树结构选择触发顶点。由于树结构是非循环的，因此可以有效地计算通过树结构的最短路径距离。本节将触发顶点的概念扩展到任何顶点桑德斯和赤冈243无环结构导致图的其余部分变成非循环的。如将示出的，这允许更有效的全对算法，但是目前，不提供改进的单源算法。设G是全图，V是G的顶点集.使用与前面相同的符号，n是顶点的总数，m是边的数量，r是触发顶点的数量。假设触发顶点的选择是通过一些有效的算法获得的。一组触发顶点T必须满足以下性质：• 如果T中的所有顶点都从图中移除，则剩余的顶点T导出一个非循环图。注意，由T中的顶点形成的图允许是不连通的。也就是说，触发顶点的选择对应于反馈顶点集。图2显示了一个示例图来说明这个概念。下面的图示示出了用于选择r个触发顶点u1，u2，. . .乌河进出非循环结构的边的视图已经使用每个触发器顶点的副本和伪边来简化，伪边表示去往或来自同一触发器顶点的许多边u1u1u2u2乌尔乌尔图二.将图结构标识为由触发顶点和非循环部分组成的示例。新的全对算法包括两个阶段。算法5表示第一阶段，算法6表示第二阶段。该算法使用一个二维数组D来保存计算过程中的最短路径距离。在算法的最后，数组D保持任何一对顶点之间的最短路径距离。在该算法中，引用数组d用于引用D中的一行。更新最短路径计算桑德斯和赤冈244≤≤通过T中的顶点，可以有效地完成，因为由T是非循环的。该算法使用了T中顶点的拓扑排序，存储在有序集L中，可以在O（m+n）时间内获得。图P的顶点对应于触发器，由算法的第一阶段构造，并由GSS用于计算通过T中顶点的最短路径距离。新的全对算法的第一阶段计算第一个试探性距离d1[v0，v]。符号d1[v0，v]用于阐明该描述，并且对应于算法5结束时D[v0，v]的状态。这涉及到执行几个单源问题的第一阶段。对于每个v0V：• 计算从v0到每个顶点v <$V的第一试探最短路径距离d1[v0，v]距离d1[v0，v]对应于以下形式的路径中的最短路径：（v0，v1，v2，.，v k，v），k≥ 0其中每个vi ≠ T，对于1≤i≤k。计算从源顶点到第一个试探性距离v0需要O（m）时间。作为算法第一阶段的副产品，从G计算出一个简化图P。P中的每个顶点对应于一个触发顶点。 P中边的边成本（称为伪边）定义如下：• 伪边（u，w）的成本，其中u ≠ T且w ≠ T，对应于以下形式的路径中的最短路径：（u，v1，v2，...，v k，w），k≥ 0其中每个V都是1我K. 也就是说，路径只经过T中的顶点，除了端点。如果不存在这样的路，则图P中不存在边（u，w）。第一阶段，包括计算P的边缘距离，需要O（mn）时间。对于本说明的其余部分，mJ将表示P中的边数。算法5新全对算法1.对T中的顶点进行拓扑排序，将结果放入有序集L中。2.对于V中的每个顶点v0，do{3.设d是对数组D行v0的引用;4.对于V中的每个顶点v，d[v] = ∞;5.intmaximum [0] = 0;6.如果v0在T中，则对于OUT（v0）中的每个顶点w，d[w] =c（v0，w）;7.对于每个顶点v，按照从L开始的顺序do {8.对于OUT（v）中的每个顶点w，do{[5]对于算法第二阶段的正确性来说，只有第一个试探性距离d1[v0，u]（对于顶点u ∈ T）和d1[v0，v0]=0是重要的（参见算法6）。其他的第一个试探性距离并不重要，因为在算法6中可以进行相同的计算。桑德斯和赤冈245/∞≤≤9.d[w] =min（d[w]，d[v]+c（v，w））;10.}11.}12.如果v0在T中，则{13.对于T中的每个顶点u，其中d[u]/=∞do{14.将具有成本d[u]的edge（v0，u）添加到P;15.}16.}17. 个文件夹在算法的第一阶段，没有删除min操作。在算法5的最外循环（第2行到第16行）中，通过顶点的拓扑排序更新距离以及向P添加边将花费O（m）的总时间。时间复杂度为O（m），所以时间复杂度为O（m）。最后一个循环重复n次，总时间为O（mn）。在完成最外层循环的一个循环后，将计算从源顶点v0到所有其他顶点的通过T的最短路径距离。在算法的第一阶段完成后，任何一对顶点（u，v）之间通过T的最短路径距离都在D[u，v]中;也就是说D[u，v]等于从u到v的第一个试探性最短路径。同样，对于任意一对顶点u <$T和v <$T：• 如果D[u，v]=，则P中从u到v的边的边成本等于D[u，v]。虽然这种方法对于所有的对都是有效的，但是对于单源问题是不有效的，因为计算P的伪边将花费O（rm）时间，这超过了Dijkstra算法的O（m+nlogn）时间复杂度新的全对算法的第二阶段（参见算法6）完成全对最短路径计算。注意，来自算法5的距离值保留在D中并用于算法6。这对算法6的正确性很重要。该全对算法的第二阶段可以被视为重复每个单源问题的第二阶段对于每个v0V：(i) 令d1[v0，u]对应于算法5结束时D[v0，u]的值。对于顶点u ∈ T，距离d1[v0，u]被用作图P上的GSS问题的初始距离d0[u]。算法2，或其他一些有效的GSS算法，然后用于计算GSS最短路径距离在P。从P上的GSS问题计算的距离d[u]（对于u ∈ T）对应于最短路径与以下形式的路径的距离：（v0~u1~u2~.）~u k~u），k≥ 0其中每个ui T（对于1i k）是路径上的唯一触发顶点，并且符号~表示以下形式的路径：（v1，v2，.，v j），j≥ 0桑德斯和赤冈246其中vi ≠ T，1≤i≤j。这表示从v0到顶点u。因此，从GSS问题计算的u ∈ T的距离d[u]是所有对问题中的最终最短路径距离D[v0，u]。这个断言的正确性来自于GSS问题的定义;参见第2节和Takaoka [4]。(ii) 形式D[v0，u]的最终最短路径距离，其中u <$T，然后用于计算顶点v <$T的形式D[v0，v]的最短路径距离。在从v0开始的单源计算结束时，对于v ∈ T，距离d[v]对应于最短路径与以下形式的路径的距离：（v0~u1~u2~.）~u k~v），k≥ 0其中每个ui <$T（对于1≤i≤k）是路径上唯一的触发点。因此，v<$T的距离d[v]，指D[v0，v]，在所有对问题中是最终的。时间复杂度为O（m+ r），时间复杂度为O（M+r）。这是重复n次以覆盖所有源顶点，所以第二阶段的总时间是O（mn+mJ n+nr logr）。算法6新全对算法的第二阶段18. 对于V中的每个顶点v0，do{19.设d是对数组D行v0的引用;20.对于T中的每个顶点v，将v的GSS初始距离设置为d[v];21.解决P上的GSS问题;/* 这最终确定了T中 v的距离d[v]（即D[v0，v]）22.对于T中的每个顶点u，do{23.对于OUT（u）中的每个顶点w，做d[w] =min（d[w]，d[u]+c（u，w））;24.}25.对于每个顶点v，按照从L开始的顺序do {26.对于OUT（v）中的每个顶点w，do{27.d[w] =min（d[w]，d[v]+c（v，w））;28.}29.}30. 个文件夹算法6的每个外循环完成从源顶点v0到所有其他顶点的单源最短路径计算;行19到29。在第21行，解决了GSS问题，并且d[v]保持从顶点v0到顶点v<$T的最短路径距离。求解P上的GSS问题需要O（MJ+rlogr在算法的整个第二阶段，删除min和其他堆操作只发生在GSS算法中。在线22的开始处，已知从v0为了完成单源计算，必须确定从v0到非触发第22行到第29行通过扫描最短路径距离来桑德斯和赤冈247通过L中顶点的拓扑排序进行更新。时间复杂度为O（m）在第29行之后，已经计算了从顶点v0第二阶段完成单源计算的总时间为：时间复杂度O（mJ+rlogr）对于每个v0<$V重复完成单源计算，因此总共完成了n个因此，第二阶段的总时间复杂度为O（mn+mJ n+nr logr）。取算法的第一和第二阶段的组合时间，总时间复杂度为：O（mn）+O（mn+mJ n+nr logr）=O（mn+mJ n+nr logr）考 虑 到 最 坏 的 情 况 ， 其 中 MJ 是 O （r2 ） ， 时 间 复 杂 度 是 - comesO（mn+nr2）.对于大多数近似无环图，我们期望r远小于n，算法的时间复杂度为O（mn）。时间复杂度为O（nr），时间复杂度为O（nr）。如果对于一个给定的图，k是大的，r是小的，新的算法可以给以前的最短路径算法[4]的显着改善。该算法的其他实现是可能的，其通过常数因子而更有效。更有效的实现可以避免从顶点v的距离更新，当d[v]仍然无限时。一种这样的算法使用两个单独的深度优先搜索（DFS）类函数，其中一个DFS函数仅遍历边缘并且不更新最短路径距离。6总结发言对于近似无环图，可以在O（m+rlogr）时间内解决广义单源问题，其中r是触发顶点的数量，触发顶点定义为图分解为树时产生的树的根。这是对Abuaiadh和Kingston [1]及Takaoka [4]中关于几乎无圈图的最短路算法的一个改进。它是可能的，结合这个新的算法和以前的算法到一个混合算法，其中包括每个属性。未来的工作涉及从树分解推广到非循环分解，以允许减少触发顶点的数量对于全对最短路问题，给出了一个最坏情况下时间复杂度为O（mn+nr2）的新算法，其中r是近似无圈图的反馈顶点集的顶点数.在几乎无圈图的大多数情况下，r远小于n，算法的时间复杂度为O（mn）。当反馈顶点集预先已知时，这是一个显著的改进。鉴于最小反馈顶点集问题是NP完全的，如果反馈顶点集事先不知道，我们需要满足于触发器的非最优反馈顶点集。我们的最终目标是找到一个好的启发式算法，在桑德斯和赤冈248我们的最短路径算法的时间复杂度，它计算一个反馈顶点集的大小在一个常数乘以最佳大小。另一个考虑因素是是否有一个有效的单源算法是可能的，任何反馈顶点集可以用作触发顶点。引用[1] D. Abuaiadh和J.H.金斯顿斐波那契堆是最优的吗？在ISAAC一九九四年[2] E. W.迪杰斯特拉关于图中两个问题的注记。Numerische Mathematik，1：269[3] M.L. Fredman和R.E.塔扬斐波那契堆及其在改进网络优化算法中的应用。Journalof the ACM，34（3）：596[4] T. 高冈几乎无圈有向图的最短路算法理论计算机科学，203（1）：143[5] T. 高冈2-3堆的理论 在proc COCOON '99，计算机科学讲义第1627卷，第41-50页。1999年7[6] T. 高冈三项堆理论在COCOON2000年7月[7] R.塔扬深度优先搜索和线性图算法。SIAM Journal on Computing，1（2）：146