CODEWITHSUNDEEP
algorithmgraph-theory
aivision2020
aivision2020

Reputation: 629

Maintain shortest paths while updating graph

I want to know the distance between all pairs (ex. dijkstra. Specifically I'm using networkx) Then when an edge is added to graph I want to update the distances without recomputing from scratch.

How can this be done? Thanks

Upvotes: 2

Views: 1208

Answers (2)

user22056823
user22056823

Reputation:

It should be possible in O(V log(v) [which is for the priority queue] + E [bc. you cannot know what new edges the algorithm will take])

Upvotes: 0

SaiBot
SaiBot

Reputation: 3755

It is possible without recomputing all shortest paths but still pretty costly O(n^2).

So lets assume you have a distance matrix M with size n*n where each entry M_{i,j} contains the distance from node i to node j. M is assumed to be precalculated by some algorithm.

Now if a new edge e_{i,j} is added to the graph between node i and node j with cost w_{i,j}, you check if w_{i,j} < M_{i,j}. If not, then nothing has to be changed. But if it holds, then the shortest paths in the graph might improve.

Then for each node pair k, l you check if the path going through the new edge is shorter than the previously calculated one. This can be done by evaluating the following.

M_{k,l} > min (M_{k,i} + w_{i,j} + M_{j,l} , M_{k,j} + w_{j,i} + M_{i,l})

If this holds then you can replace M_{k,l} by min (M_{k,i} + w_{i,j} + M_{j,l} , M_{k,j} + w_{j,i} + M_{i,l})

The above works for unidirectional graphs but can be adapted to bi-directional graphs as well.

Edit 1

I firmly believe that \Omega(n^2) is also the lower bound of this problem. Assume you have two disconnected areas of the graph both containing n/2 vertices. Then if you add a new edge connecting these areas you will have to update n/2 * n/2 shortest paths resulting in at least O(n^2) runtime.

Edit 2

A second idea would try to exploit the above equation but run through the graph first in order to find all pairs of vertices that have to be updated first. The sketch of the idea is as follows:

Start a Dijkstra from node i. Whenever you reach a vertex k you check if M_{k, i} + w_{i, j} < M_{k, j} if yes then add k to the set U of vertices that have to be updated. If not, then you can stop exploring further paths following k, since no vertex "beyond" k will use e_{i, j} for the shortest path.

Then do the same for node j. And then perform the update of M for all pairs of vertices in U according to the ideas above.

Upvotes: 2

Related Questions