Given a connected graph, with weighted edges, a virus starts from a given node. It takes x seconds for the virus to travel from a node to one of its neighbours where x is directly proportional to the weight of the edge.
If you are allowed to remove one edge from this graph in order to maximize the ammount of time it takes for the virus to infect all the nodes. How to find this edge?
I could come up with an O($ n^2$ ) solution to remove every edge one by one and then run BFS to find out the time it takes for the virus to infect every node. Is there a better solution in terms of time complexity?