I think 11.

The Gateway to Computer Science Excellence

+6 votes

Best answer

a **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 |

{ } | 0 |
∞ | ∞ | ∞ | ∞ | - |

{ 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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,292 answers

198,237 comments

104,919 users