# updating one edge in MST problem
## problem:
Suppose we are given both an undirected graph G with weighted edges and a minimum spanning tree T of G.
Describe an algorithm to update the minimum spanning tree when the weight of a single edge e is decreased.
The input to your algorithm is the edge e and its new weight; your algorithms should modify T so that it is still a minimum spanning tree.

## case 1:
In the case where e ∈ T, the minimum spanning tree T does not change. This is due to the fact that, because the edge e is part of the minimum spanning tree, it is inherently the most optimal edge. Decreasing the weight of e only makes the edge even more favorable.

## case 2:
In the case where e ∉ T, we can start by adding e to T and analyzing the cycle created by this edge. If, in this cycle, there is some edge f which has a weight greater than the new weight of e, it follows that replacing the edge f with the edge e allows for a more optimal minimum spanning tree.

## algorithm:
Given a minimum spanning tree T, the edge e (connecting vertices u and v) that is not part of T, and the new weight w, the algorithm starts by finding the max weight edge on the path between u and v in the MST. It would then compare this max weight to the new weight, and if replacing this edge wouldn't improve the MST, returns. Otherwise, the algorithm replaces the max edge with the new edge.

// Tadj holds adjacency lists
// weight[] stores the weights of edges

// helper functions, implementation not shown
fun removeEdge(var edgeID) {
    // removes the edge from the tree by erasing its endpoints from the adjacency lists
}

fun addEdge(var edgeID, var u, var v) {
    // adds the edge to the tree by pushing the edge and the endpoint to the adjacency lists
}

// returns a pair on the path from u to target
fun dfsMaxEdge(var u, var target, var parent, var currMaxWeight var currMaxEdge) {
    if (u == target) {
        return pair(currMaxWeight, currMaxEdge);
    }
    for (int i = 0; i < Tadj[u].size(); i++) {
        edge e = Tadj[u][i];
        if (e.to == parent) continue;
        
        int w = weight[e.id];
        int nextMaxWeight = currMaxWeight;
        int nextMaxEdge = currMaxEdge;
        
        if (w > nextMaxWeight) {
            nextMaxWeight = w;
            nextMaxEdge = e.id;
        }
        
        pair res = dfsMaxEdge(e.to, target, u, nextMaxWeight, nextMaxEdge);
        if (res.first != -1) {
            return res; // found target
        }
    }
    return pair(-1, -1); // not found
}

// main algorithm (assumes e ∉ T)
fun updateMST(var u, var v, var edgeID, var newWeight) {
    weight[edgeID] = newWeight;
    pair result = dfsMaxEdge(u, v, -1, -1, -1);
    int maxWeight = result.first;
    int maxEdge = result.second;
    
    // if the new weight is no better, keep the old MST
    if (maxWeight <= newWeight) {
        return;
    }
    
    // else swap the edges
    removeEdge(maxEdge);
    addEdge(u, v, edgeID);
    
}

## correctness:
#### Theorem:
In the case that e ∉ T, the algorithm correctly improves the MST in a logical manner.
#### Proof:
When the weight of an edge e = (u, v) outside of the current MST T decreases, the algorithm must consider replacing some edge or edges of the tree. Since T is a minimum spanning tree, we know that inserting e would create exactly one simple cycle C consisting of the new edge e and the unique path between vertices u to v already within the MST.

Let f be the maximum weight edge on this cycle prior to the updated weight.
The algorithm firstly checks whether the new weight of e is less than the current weight of f, which can be explained by the Cycle Property of MSTs. This states that, given any cycle, an edge of the strictly maximum weight within this cycle cannot belong to any MST. Therefore, after decreasing the weight of edge e, if its new weight is less than the cycle's heaviest edge f, then f must be replaced by e in the MST. Otherwise, e is not the heaviest edge but also not lighter than anything else within this cycle, meaning that inserting e would not produce a cheaper tree than what is already in the optimal MST.

Therefore, if e's new weight is less than the weight of f, we remove edge f which breaks the cycle and add e to restore the connectivity of the MST with a smaller total weight. This results in an MST that is strictly lighter than the old MST. QED.

## complexity:
The algorithm overall runs in O(n) time, since finding the maximum weight edge on the path between u and v takes O(n) time with our depth first search approach and all other operations follow a complexity of O(1).