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?

Susannesusceptibility

BTW when all the edges in graph are negative, finding shortest path is the same problem as finding longest path for the graph with edges labeled with absolute value of their original length. Longest path problem is known to be NP-hard. – Foolish

Thanks for the question. Could you please let me know why the algorithm is not affected by negative edges as you understood? I have read the replies as well. – Hass

Answer 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.

Cassilda

The fact that a tree that is a sub-graph of a graph has a fixed number of edges depending on the number of vertices, so adding a number p to every edge cost increases the overall mst cost of pE. It is not true in finding shortest path, because the shortest paths can consist of different number of edges. – Therefor

The two most popular algorithms for finding MST (Kruskal's and Prim's) work fine with negative edges because they work on undirected graphs – Ellie

Answer 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.

Tessin

Answer 3

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.

Niki