Sub-Tree of Shortest path Tree is also a shortest Tree?

Question

I have an undirected weighted graph G=(V,E) where V represent nodes and E represent edges. Through Dijkstra Algorithm, I got a shortest path tree Ts=(s,V) rooted at source node s and spanning all nodes V in the graph G. Then I selected a sub-tree Tm=(s,K), (where K is a subset of V) of shortest path tree Ts=(s, V) that connect s to only K nodes among all V nodes, i.e, the sub-tree Tm is a subset of shortest path tree Ts.

My question is how can now I prove by arguments or a lemma/Theorem that this sub-tree Tm of shortest path tree Ts is also a shortest tree?. Thank you in advance.

Answer 1

Well, I guess that this SPT (Shortest Path Tree) is just a tree that has an edge from the source to each other node (cos if it isn't this way, it may contain cycles).

Then, if you choose some sub-tree of the original SPT, you will have to keep the properties of a tree, then we have some cases:

• Trivial Tree: just one node, no edges

  no problems in here, it's a SPT (empty)
  

• Not-Trivial Tree: two or more nodes, obviously with edges.

  this is kind of tricky. 
  
  if you suppose that this sub-tree is rooted on source, then its easy
  to see that the sub-tree will be a set of shortest paths between
  the source and the other nodes, making it be a SPT ROOTED ON SOURCE.
  
  otherwise, it wont be a SPT, cause if its rooted on some other node
  (instead of source), the path from the root to other node (different
  from source) may not be minimum.
  

As I guess you are interested in a sub-tree that is rooted on the source, than it's easy to see that a sub-tree will contain only shortest paths (as it's a subtree of a SPT itself), and then it will be a SPT.

Answer 2

Since the question is not clear enough, I assume your question is the following -

If Ts=(s,V) is a shortest path tree (rooted at s) of the graph G = (V,E,W), then prove that T's = (s, K), a subtree of Ts induced by K (\subset V), is a shortest path tree (rooted at s) of the subgraph G' = (K,E',W) of G induced by K.

You can prove by contradiction.

Proof (informal): Let u \in K be a vertex. Since, u is also in V, the path p = s -> u given by Ts is the shortest. Assume, T's is not a shortest path tree of G'. Then the path p = s -> u given by T's is not the shortest in G'. This means, there exists another vertex v (\in K) such that p does not contain v and v creates a shortcut like s -> v -> u.

Since the path p = s -> u given by Ts is the shortest in G, p must have contained v somewhere in between s and u, which leads to contradiction.