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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.