Is Minimum Spanning Tree afraid of negative weights?

Question

This is a follow-up question of Why most graph algorithms do not adapt so easily to negative numbers?.

I think Shortest Path (SP) has problem with negative weights, because it adds up all weights along the paths and tries to find the minimum one.

But I don't think Minimum Spanning Tree (MST) has problems with negative weights, because it just takes the single minimum weight edge without caring about the overall total weights.

Am I right?

Solution 1

Yes, you are right. The concept of MST allows weights of an arbitrary sign. The two most popular algorithms for finding MST (Kruskal's and Prim's) work fine with negative edges.

Actually, you can just add a big positive constant to all the edges of your graph, making all the edges positive. The MST (as a subset of edges) will remain the same.

Solution 2

Yes, you are right because if you see the algorithm for shortest path like dijkstera it will check if the present distance of vertex v is greater than sum of present value + edge weight then it will change the value of distance of vertex v from s by the sum value and if the edge weight is negative then it will give some problems.

But in the MST problem there are algorithms like prims,kruskal which take only the minimum weight edge so that make the negative edge qualify for MST.