# Finding a tree that approximates the distances and total weights

Given an undirected graph $G=(V,E)$ could we build a tree $T$ that approximates the distances from given vertex $r$ and the total weight, i.e. $\forall x \in V, d_G(r,x) \le d_T(r,x) \le 3 \cdot d_G(r,x)$ and $w(T) \le 3\cdot w(\text{MST}(G))$, where $\text{MST}$ is the minimum spanning tree and $w(\cdot)$ is the weight function i.e. $w:\Bbb E \to \Bbb R^+$. $d_G(v,u)$ denotes the shortest path distance between $v$ and $u$ in $G$, and $d_T(v,u)$ is the shortest path distance between $v$ and $u$ in $T$.

Could any one help me to understand how to build this tree and if there is any material that would help?

• @FayezAbdlrazaqDeab: how would one construct the minimum spanning tree that you need to compare to? Look up Prim's algorithm. – Wandering Logic Apr 27 '13 at 23:05
• assume you build $T$ who much is it close to $MST$ ? or something like this ... I dont think you need to build it – Fayez Abdlrazaq Deab Apr 27 '13 at 23:12
• @FayezAbdlrazaqDeab, as wandering logic mentioned, seems shortest path tree is 2 approximation, you can think about this and update your question with your thought. – user742 Apr 27 '13 at 23:18
• this give us a perfect distances but how much it approximates the mst weight? it dosnt fulfill it! take a circle all weights are 1 and just one of them is n-2 – Fayez Abdlrazaq Deab Apr 27 '13 at 23:25
• In the circle you mentioned all of your inequalities are correct. p.s: with same argument you can prove is 2-approximation. – user742 Apr 27 '13 at 23:40

Your problem is solved in the following paper by Khuller, Raghavachari, and Young. They show that you can construct a tree in which distances from the root are stretched by at most $\alpha$ and the total weight of the tree is at most $1 + 2/(\alpha - 1)$ times the weight of the MST. So, with $\alpha=3$, you can get $2$ times the weight of the MST. The algorithm does a depth-first traversal of the MST, and adds paths from the shortest path tree when necessary, roughly speaking maintaining a shortest path structure in the current graph, which consists of the MST edges and the edges added from the shortest path three. Check the paper for details.
As I mentioned in the comment, there are graphs in which the weight of the shortest path tree rooted at some vertex is greater than the MST weight by $\Omega(n)$. One example is a path of unit weight edges, and edges from the first vertex in the path to the $i$-th vertex of weight just slightly less than $i-1$.