GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
80 views

asked in Algorithms by Active (1.4k points)   | 80 views
I think 11.
s-a-b-c-d gives 10 only
According to ur tree distance between s and d is 10 while it should be 7

1 Answer

+6 votes
Best answer

 

shortest-path tree rooted at vertex v is a spanning tree T of G, such that the path distance from root v to any other vertex u in T is the shortest path distance from v to u in G.

Path s a b c d parent
{ } -
{ s } - 2 7 s (parent of a)
{ s,a } - min(7,5) = 5 10 7 a (parent of b)
{ s,a,b } - - - min(10,6) = 6 7 b (parent of c)
{ s,a,b,c } - - - - min(7,8) = 7 a (parent of d)

So the graph has edges sa, ab, bc and ad

so sum = sa+ab+bc+ad = 2+3+1+5 = 11

answered by Boss (7.8k points)  
selected by


Top Users Jul 2017
  1. Bikram

    4386 Points

  2. manu00x

    2464 Points

  3. Debashish Deka

    1850 Points

  4. joshi_nitish

    1686 Points

  5. Arjun

    1340 Points

  6. Hemant Parihar

    1184 Points

  7. Arnab Bhadra

    1112 Points

  8. Shubhanshu

    1080 Points

  9. Ahwan

    900 Points

  10. rahul sharma 5

    732 Points


24,031 questions
30,983 answers
70,430 comments
29,358 users