Given a directed graph with weighted edges, what algorithm can be used to give a sub-graph that has minimum weight, but allows movement from any vertex to any other vertex in the graph (under the assumption that paths between any two vertices always exist).
Does such an algorithm exist?
Even though they weren't right themselves, taking the time to follow Vitalii's Wikipedia links quickly uncovered this algorithm:
http://en.wikipedia.org/wiki/Chu%E2%80%93Liu/Edmonds_algorithm
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With