Prove that the array prev[.] computed by Dijkstra’s algorithm, the edges (v, prev[v]) for all v ∈ V , form a tree
In order to prove this I used induction.
Lemma : "A tree with n vertices has n-1 edges" R contains vertices with shortest distance from s and rest are in R'
Base case : s is added to R. There are 0 edges. I-H: Vertex v is added to R such that it has the shortest distance from s in R'.
I don't know how to continue from here since I am new to this.