CODEWITHSUNDEEP
algorithmdata-structuresgraphminimum-spanning-tree
Jackson Tale
Jackson Tale

Reputation: 25842

Is Minimum Spanning Tree afraid of negative weights?

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?

Upvotes: 64

Views: 60132

Answers (3)

REVANASIDDA
REVANASIDDA

Reputation: 1

Yes,you are right Prim's algorithm works like dijkstra's algorithm but in prim's algorithm it should not compute shortest path from i to j having negative edges . So, their is an another algorithm is their i.e Bellman-Ford algorithm for compute shortest path from i to j with negative edge.

Therefore prim's and Kruskal's algorithm is not fear for negative edges.

Upvotes: -6

Rahul Dhawan
Rahul Dhawan

Reputation: 61

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.

Upvotes: 6

Skiminok
Skiminok

Reputation: 2871

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.

Upvotes: 86

Related Questions