# Is there an algorithm to add edges to a DAG to make it strongly connected with minimum cost?

I have a weighted DAG and a function computing the weight of edges that is not connected in the DAG. The weight of u to v equals to the weight of v to u.

I want to connect edges to make the DAG a single strongly connected component (any vertex in the new graph can reach any other vertex) with minimum total weights of added edges.

I know that the minimum number of added edges equals to $$\text{max}(|source|, |sink|)$$ but which vertex connects to which vertex so that the total weights is minimum?

• What are you looking for exactly? Any algorithm? The complexity class of the problem? Approximation results? – Peter Taylor Jun 16 at 17:31
• Can you add a url to the original problem? – Apass.Jack Jun 17 at 2:50
• My problem is similar to this problem codeforces.com/blog/entry/15102. In my problem, the graph needed to be modified is a DAG because I collapased each SCC into a vertex. – phqb Jun 17 at 4:51