CODEWITHSUNDEEP
algorithmgraph-algorithm
Wei.M
Wei.M

Reputation: 51

How to get the new MST from the old one if one edge in the graph changes its weight?

We know the original graph and the original MST. Now we change an edge's weight in the graph. Beside the Prim and the Kruskal, is there any way we can generate the new MST from the old one?

Upvotes: 4

Views: 6481

Answers (3)

Jun HU
Jun HU

Reputation: 3314

You can change the problem a little while the result is same.

  1. Get the structure of the original MST, run DFS from each vertice and you can get the maximum weighted edge in the tree-path between each vertice-pair. The complexity of this step is O(N ^ 2)
  2. Instead of changing one edge's weight to w, we can assume we are adding a new edge (u,v) into the original MST whose weight is w. The adding edge would make a loop on the tree and we should cut one edge on the loop to generate a new MST. It's obviously that we can only compare the adding edge with the maximum edge in the path(a,b), The complexity of this step is O(1)

Upvotes: 2

Evgeny Kluev
Evgeny Kluev

Reputation: 24647

Besides linear-time algorithm, proposed by j_random_hacker, you can find a sub-linear algorithm in this book: "Handbook of Data Structures and Applications" (Chapter 36) or in these papers: Dynamic graphs, Maintaining Minimum Spanning Trees in Dynamic Graphs.

Upvotes: 2

j_random_hacker
j_random_hacker

Reputation: 51226

Here's how I would do it:

  • If the changed edge is in the original MST:
    • If its weight was reduced, then of course it must be in the new MST.
    • If its weight was increased, then delete it from the original MST and look for the lowest-weight edge that connects the two subtrees that remain (this could select the original edge again). This can be done efficiently in a Kruskal-like way by building up a disjoint-set data structure to hold the two subtrees, and sorting the remaining edges by weight: select the first one with endpoints in different sets. If you know a way of quickly deleting an edge from a disjoint-set data structure, and you built the original MST using Kruskal's algorithm, then you can avoid recomputing them here.
  • Otherwise:
    • If its weight was increased, then of course it will remain outside the MST.
    • If its weight was reduced, add it to the original MST. This will create a cycle. Scan the cycle, looking for the heaviest edge (this could select the original edge again). Delete this edge. If you will be performing many edge mutations, cycle-finding may be sped up by calculating all-pairs shortest paths using the Floyd-Warshall algorithm. You can then find all edges in the cycle by initially leaving the new edge out, and looking for the shortest path in the MST between its two endpoints (there will be exactly one such path).

Upvotes: 2

Related Questions