1
$\begingroup$
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.

$\endgroup$

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.