retagged by
4,800 views

1 Answer

Best answer
5 votes
5 votes

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.-ref:http://stackoverflow.com/questions/10414043/is-minimum-spanning-tree-afraid-of-negative-weights

Related questions

5 votes
5 votes
3 answers
4
Kapil asked Jan 24, 2017
3,355 views
It may be the case that "Kruskal's Algorithm may not maintain connectivity while Prim's algorithm always does that" ?Any example which favours this ?