Is there an algorithm to compute shortest tree (not path)?

Question

Greetings Overflowers,

I have a weighted directed graph and I want the lowest cost tree that covers all nodes where the root is a specific given node of the graph. I do not know if I can also set a different maximum branching on each node where the number of branches from this node to other nodes (outward edges) is equal or less to that maximum ?

So what is the most suitable algorithm for my needs to start reading ? I hope it is fast enough :)

Many thanks !

Answer 1

You're looking for a directed minimum spanning tree (arborescence), which is an optimum branching.

http://en.wikipedia.org/wiki/Chu%E2%80%93Liu/Edmonds_algorithm