All geek questions in one place

Updating the shortest distance matrix if one edge weight decreases

We are assigned a weighted graph G and its shortest delta triangle matrix. Thus, delta (i, j) denotes the weight of the shortest path from i to j (i and j are two vertices of the graph). The delta containing the value of the shortest paths was initially set. Suddenly, the weight of the edge E decreases from W to W '. How to update delta (i, j) in O (n ^ 2)? (n = number of graph vertices) The problem is that it does NOT calculate all pair shortest paths that have the best complexity O (n ^ 3). the problem is UPDATE delta, so we won’t need to recalculate the shortest paths of all pairs.

More explanation: all we have is a graph and its delta matrix. The delta matrix contains only the shortest path value. now we want to update the delta matrix according to the change in the graph: reduced edge weight. how to update it in O (n ^ 2)?

+3
source share
3 answers

If the edge E from node a to node b has its own weight, 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 an edge from a to b. If it contains an edge from a to b, then its length delta(i, a) + edge(a,b) + delta(b, j).

, O (n ^ 2) , , .

+4

. O (n ^ 2).

EDIT . , j , , . n ^ 2, node n * n n ^ 2. - , n ^ 2 Dijkstra O (| E | + | V | log | V |). , -O?

EDIT EDIT It seems like I don't remember big-O correctly. The iteration over the matrix will be n ^ 2, and Dijkstra at each will be an additional waybill. I don’t see how to do this in the general case, without figuring out exactly which W 'paths are included ... this, apparently, implies that each pair should be checked. Thus, you need to either update each pair at a constant time or not check the significant parts of the array.

-1
source

Source: https://habr.com/ru/post/1780817/

More articles:


All Articles