UGC NET Computer Science December 2019 | Question 90

Question 90

---

Consider a weighted directed graph. The current shortest distance from source S to node x is represented by d[x]. Let d[v]= 29, d[u]=15, w[u,v]=12. What is the updated value of d[v] based on current information?

1. (1) 29
2. (2) 27
3. (3) 25
4. (4) 17

Answer : (2) 27

Explanation

d(v) represents the length of current shortest path from source S to node v, d[v] = 29

Now, given current information are:
d[u] = 15 (current shortest path from source S to node u)
w[u,v] = 12 , where w(u,v) is the weight of the edge (u,v)

d(v) is shortest path from source S to node v
= shortest path from source S to node u + shortest path from node u to node v

So, from given current information
∴ d(v) = d(u) + w(u, v)
= 15 + 12
= 27

d[v] = 27 is less then given distance d[v] = 29
∴ 27 is shortest length of path from source S to node v based on given information.

So, option 2 is the correct answer.

Previous	Next
UGC NET CS December 2019 - Question 89	UGC NET CS December 2019 - Question 91