analysis of one example in shortest path tree

Question

Consider connected and undirected Graph $G$.

shortest path tree for each vertexes of $G$ was given.

if we makes union of all these shortest path trees then order (number) of edges in this union at worst case is $O(n^2)$ !!

how this achieved? is there any idea?

My Idea:

I think a complete graph with $n$ vertex, each vertex has shortest path tree at most of $n-1$ edges in worst case and then $O(n^2)$.

Answer 1

Welcome to MSE!

Your idea is exactly right. More formally:

• We have a shortest path tree $T_v$ for each vertex $v \in G$.
• Each $T_v$ is a tree, and has $n$ vertices (since $G$ is connected).
• This means each $T_v$ has $n-1$ edges.
• So we have $n$ choices of $v$, and $n-1$ edges in each $T_v$
• So the total number of edges in all the trees is $n \cdot (n-1)$.
• but this is $n^2 -n$, which is $O(n^2)$.

---

I hope this helps ^_^