Cycles

[BlackGammon]

Hello,

I have executed your code and the result I'm getting has the correct amount of edges but it's still full of cycles. Something has probably gone wrong in the detection of cycles.

EO

[BlackGammon]

I tried with G = {0: {1: 100.0}, 1: {2: 2.0}, 2: {1: 3.0}} and root = 0

it returns g = {0: {1: 3.0}, 1: {2: 2.0}, 2: {}} which means the values in g are wrong.

[jungokasai]

I ran into the same problem.

[matus-pikuliak]

Yep, the code is faulty. I found working solution on SO (see David Eisenstat's answer):

https://stackoverflow.com/questions/23988236/chu-liu-edmonds-algorithm-for-minimum-spanning-tree-on-directed-graphs