June 29th, 2010, 08:46 PM
MST + transitive closures + ... ?
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!
Click Here to Expand Forum to Full Width