Solution: Minimum Spanning Trees

Task

Suppose we are given both an undirected graph G with weighted edges and a minimum spanning tree T of G. Provide code to update the minimum spanning tree when the weight of a single edge e is decreased. We can follow the algorithm described below.

Logic building

Here’s the algorithm to update the minimum spanning tree $T$ when the weight of a single edge $e$ is decreased:

Algorithm

---

• Identify the two nodes $u$ and $v$ that the edge $e$ connects.
• Find the path $P$ in the minimum spanning tree $T$ that connects $u$ and $v$.
• Let $e'$

...