Is graphminspantree not able to handle negative weights?
2 views (last 30 days)
Show older comments
I want to compute the minimum spanning tree in a graph whose edges might have negative weights. As far as I am aware, both Prim's and Kruskal's algorithm can handle negative weights. Also the documentation does not exclude the usage of negative weights.
Any ideas why the code below is nevertheless not working for negative weights with Matlab 2012b (Bioinformatics Toolbox Version 4.2)?
>> M = [0 0; 1 0];
>> M = sparse(M);
>> graphminspantree(M)
ans =
(2,1) 1
>> graphminspantree(-M)
Error using graphalgs
There was an error in Prim's algorithm.
Error in graphminspantree (line 127)
T = graphalgs(algorithmkeys{algorithm},debug_level,false,G,R);
(I am aware of the possibility of just adding a large positive offset to all weights to circumvent the problem. Still an answer to the original question would be interesting.)
1 Comment
Luuk van Oosten
on 10 Jun 2015
I believe MATLAB's Prim's algorithm does not handle negatives, although the only hint at that assumption I found here. Can't help you any further than the solution you already proposed. These guys over here seem to agree on that...
Answers (0)
See Also
Categories
Find more on Directed Graphs in Help Center and File Exchange
Products
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!