If I have a weighted graph $G=(V,E)$ and three subgraphs $T_1$, $T_2$ and $T_3$ in $G$ which are trees and all unconnected from each other.
What is the best way to connect these three trees such that the resultant connected tree is of minimal cost?
If it helps, I have already used the floyd-warshall algorithm to calculate the total distance matrix of $G$.
I was thinking of just iterating over all pairs of vertices $(T_1,T_2)$, $(T_1,T_3)$ and $(T_2,T_3)$ in the distance matrix and find two values from two of those groups that sum to the least. But that feels like it would be very inefficient.
essentially iterating over every vertex almost twice to get the distance values, and then iterating over those values twice again to find the smallest sum. Ending up with a complexity of like $\mathcal{O}(V^3)$ or $\mathcal{O}(V^4)$ or something (forgive me, its been a few years since i did any complexity theory)
Is there a simpler, more efficient solution that I am missing?
EDIT:
I have previously worked out a solution (not necessarily very efficient), to the problem if there are only two trees. Using the distance matrix, I iterate over every pair of vertices in $T_1$ and $T_2$, and then use dijkstra's algorithm to find the shortest path that joins the pair of vertices with the lowest value in the distance matrix.
Am I on the right track at least for the instance where there are only 2 trees? This method seems to get a lot trickier and much less efficient when there are more than 2 trees.
CLARIFICATION:
There seems to have been a bit of confusion (in a subsequently deleted comment) about what I am asking, so I will be more explicit.
The subgraphs $T_1$, $T_2$ and $T_3$ are trees in $G$, but are not connected to eachother.
here is an example:
I am trying to work out a good method of connecting all three trees such that it results in the smallest total cost
From the example I have given, it is pretty trivial to connect $T_2$ and $T_3$, just find an MST over the union of their two vertex sets because they share a single edge. However my problem stems from trying to connect $T_1$ to the rest; there are a lot of ways in which I can draw a path from $T_1$ to the other two, but I want to find the shortest one.
The only way I have thought of so far is to iterate over all the vertices in $T_1$ and see which one is closest to the vertices in $T_2$ and $T_3$ and then use dijkstra to find the shortest path. But this becomes pretty inefficient with very large scale graphs.
So I am looking for a more efficient method of doing this.
I hope that is more clear.
UPDATE:
In response to @D.W.'s answer to my related question here on solving a simplified version of this problem with only two vertex sets.
In order to extend that solution to this, more complicated, instance of the problem with three distinct vertex sets. Do I just need to create 3 dummy vertices $\{t_1,t_2,t_3\}$in $G$ with edge lengths 0 that link to $T_1$, $T_2$ and $T_3$ respectively, and then run dijkstra 3 times: $t_1 \rightarrow t_2$, $t_1 \rightarrow t_3$ and $t_2 \rightarrow t_3$, to find the minimum path $p_1$ that joins two of the three vertex sets; then if, say, the shortest path lay between $t_2$ and $t_3$ then run dijkstra again to find the shortest path $t_1 \rightarrow t_4$ where $t_4$ is a dummy vertex with 0 edge cost linking to the set $\{T_2 \cup T_3 \cup p_1\}$?
Or is that making things too complicated?