Is Minimum Spanning Tree afraid of negative weights?

algorithm data-structures graph minimum-spanning-tree
Jackson Tale picture Jackson Tale · May 2, 2012 · Viewed 37.8k times · Source

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?

Answer

Skiminok picture Skiminok · May 2, 2012

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.

Related questions

Differences between Minimum Spanning Tree and Shortest Path Tree

Here is an exercise: Either prove the following or give a counterexample: (a) Is the path between a pair of vertices in a minimum spanning tree of an undirected graph necessarily the shortest (minimum weight) path? (b) Suppose that the …

Read More
What exactly is augmenting path?

When talking about computing network flows, the Algorithm Design Manual says: Traditional network flow algorithms are based on the idea of augmenting paths, and repeatedly finding a path of positive capacity from s to t and adding it to the …

Read More
How to find the number of different shortest paths between two vertices, in directed graph and with linear-time?

Here is the exercise: Let v and w be two vertices in a directed graph G = (V, E). Design a linear-time algorithm to find the number of different shortest paths (not necessarily vertex disjoint) between v and w. Note: the …

Read More