This is an implementation of the Edmond's algorithm taken from Alan Gibbons book algorithmic graph theory to obtain
a maximum weight spanning tree or a maximum branching.
I fixed a few mistakes in the published algorithm and have made this implementation available.
I believe you should be able to obtain the minimum spanning tree too by changing weights and changing them back after the application of the algorithm.
Hi, I met some problem on how to change the edge weights so that the algorithm can be used to obtain a minimum spanning tree for a directed graph?Firstly, I have tried to inverse the edge weight. However, the resulting spanning tree is not the minimum spanning tree as the spanning tree with the maximum sum of the inversed edge weights does not ensure the corresponding initial spanning is a minimum spanning tree. What's more, I have tried to use the negative edge weights to get the minimum spanning tree, but the codes could not successfully run. Looking forward to hearing from you, thanks.
What's the complexity of the algorithm?
Is it the same as with "graphmaxflow(G, SNode, TNode)" for which it says "The algorithm that determines Cut, all minimum cuts, has a time complexity of O(2^N), where N is the number of nodes. If this information is not needed, use the graphmaxflow function without the third output."