Replacement Paths for Pairs of Shortest Path Edges in Directed Graphs
Replacement Paths for Pairs of Shortest Path Edges in Directed Graphs
复制标题
有向图中最短路径边对的替换路径
DOI：
--
复制
发表时间：
--
期刊：
影响因子：
--
通讯作者：
Amit M. Bhosle
中科院分区：
文献类型：
--
作者：
Amit M. Bhosle
（单个边缘）替换路径问题定义如下：给定加权图G（V，E），两个节点S和T，最短的路径PG（S，T）= {E1，E2。 ，ep}从g中的t到t，计算出1≤i≤p的图形\ ei中的最短路径。删除路径上的边缘该问题的ATWO-EDGE概括为定向图，称为Theedge对替换路径问题：上述定义的Giveng，S，T，T和PG（S，T），计算Pg的两个边缘（S，T）（S，T） ）失败，对于PG的所有p对（s，t）。 10]算法基于一种新的算法，用于单层替换路径问题的有名版本，该算法巧妙地使用了对输入图的修改，巧妙地使用了由全对shorttest-paths计算提供的信息，并避免了广泛的评论。天真算法。
The (Single-Edge) Replacement Paths problem is defined as follows: Given a weighted graph G(V, E), two nodes s and t, and the shortest path PG(s, t) = {e1, e2, . . . , ep} froms to t in G, compute the shortest path from s to t in the graphG\ei for 1 ≤ i ≤ p. In other words, the single-edge replacement paths problem studies how a given s-t shortest path changes with the deletion of an edge lying on the path. We study atwo-edgegeneralization of this problem for directedgraphs, termed theEdge Pairs Replacement Paths problem: GivenG, s, t, andPG(s, t) as defined above, compute the shortest path from s to t when two edges of PG(s, t) fail, for all the p pairs of edges of PG(s, t). We present anO(n) algorithm for this problem, and establish an Ω(mn) lower bound in thepath comparisonmodel for shortest path algorithms which was introduced in [10]. Our algorithm is based on a new algorithm for the directed version of the single-edge replacement paths problem which makes clever use of the information provided by the all-pairs-shortest-paths computation on a modification of the input graph and avoids extensive recomputations required by the naive algorithm.