Question

Input a simple undirected weighted graph G with non-negative edge weights (represented by w), and a source node v of G. Output: TDB. D: a vector indexed by the vertices of G. Q: priority queue containing the vertices of G using D[] as key D[v]=0; for (all vertex ut-v) [D[u]-infinity:) while not Q. empty() 11 Q is not empty fu - Q.removein(); // retrieve a vertex of Q with min D value for (all vertex : adjacent to u such that is in ) (11 perform relaxation procedure on edge (2, 2) if (D[u]+w(, z) <D[z]) {D[z] - D[u]+w(2,3); // D[z] is now the key of 2 in a. [6 points] Answer the following True False questions. We use the term cloud to refer to the vertices of that are outside Q. Claim TF 1 This program computes the shortest distance from v to every vertex of G. 2 This program finds a shortest path from v to every vertex of G. 3 Vertices enter the cloud in the order of increasing shortest distance from v. The order in which vertices enter the cloud determines a shortest path from 4 v to each node (if nodes enter in the order A, B, C, D, etc then (A.B.C.D.) is a shortest path Any vertex in Q has a longer (or as long) shortest distance from v than any Vertex in the cloud If a vertex U is in the cloud and a vertex W is in Q. no shortest path from v 6 to U goes through W .

Answer 1

This given is algorithm for Dijkstra Algorithm. It is used for all-vertex shortest path.

Answer:

1. True

2. True

3.True

4.True

5.True

6.True

i think all option are true. May be 4th option false