如果减少一个边缘权重，则更新最短路径距离矩阵 [英] Updating Shortest path distances matrix if one edge weight is decreased

问题描述

我们得到了一个加权图G及其最短路径距离的矩阵增量。因此，delta（i，j）表示从i到j的最短路径的权重（i和j是图的两个顶点）。最初给出
增量，其中包含最短路径的值。边缘E的权重突然从W​​减小到W'。如何更新O（n ^ 2）中的delta（i，j）？ （n =图的顶点数）
问题不在于再次计算具有最佳O（n ^ 3）复杂度的全对最短路径。问题是更新三角洲，因此我们无需重新计算所有对最短路径。

We are given a weighed graph G and its Shortest path distance's matrix delta. So that delta(i,j) denotes the weight of shortest path from i to j (i and j are two vertexes of the graph). delta is initially given containing the value of the shortest paths. Suddenly weight of edge E is decreased from W to W'. How to update delta(i,j) in O(n^2)? (n=number of vertexes of graph) The problem is NOT computing all-pair shortest paths again which has the best O(n^3) complexity. the problem is UPDATING delta, so that we won't need to re-compute all-pair shortest paths.

更多说明：我们所拥有的只是一个图形及其三角洲矩阵。增量矩阵仅包含最短路径的值。现在我们要根据图形的变化来更新增量矩阵：减少边缘权重。如何在O（n ^ 2）中更新它？

More clarified : All we have is a graph and its delta matrix. delta matrix contains just value of the shortest path. now we want to update delta matrix according to a change in graph: decreased edge weight. how to update it in O(n^2)?

推荐答案

如果从节点a到节点b的边E的权重减小了，则我们可以在恒定时间内更新从节点i到节点j的最短路径长度。从i到j的新最短路径要么与旧路径相同，要么包含从a到b的边缘。如果它包含从a到b的边，则其长度为 delta（i，a）+ edge（a，b）+ delta（b，j）。

If edge E from node a to node b has its weight decreased, then we can update the shortest path length from node i to node j in constant time. The new shortest path from i to j is either the same as the old one or it contains the edge from a to b. If it contains the edge from a to b, then its length is delta(i, a) + edge(a,b) + delta(b, j).

由此，用O（n ^ 2）算法更新整个矩阵是微不足道的，与处理无向图的算法一样。

From this the O(n^2) algorithm to update the entire matrix is trivial, as is the one dealing with undirected graphs.

这篇关于如果减少一个边缘权重，则更新最短路径距离矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！