views:

9

answers:

0

Hi,

Given some positive-weighted directed graph, I'd like to find a cheapest set of edges s.t.
1. The set of vertices is a spanning tree, i.e. all vertices are present in the final graph
2. Every vertex is reachable from any other vertex through a directed path (transitive closure??)
3. Set of edges has the minimum cost

Essentially, I want the cheapest set of edges that allows me to go from every vertex to every other vertex through some directed path of any length.

Thanks for any help!