The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+2 votes

+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.1k
- Engineering Mathematics 4k
- Digital Logic 1.7k
- Programming & DS 3k
- Algorithms 2.6k
- Theory of Computation 3.2k
- Compiler Design 1.2k
- Databases 2.4k
- CO & Architecture 2.1k
- Computer Networks 2.4k
- Non GATE 795
- Others 1.2k
- Admissions 244
- Exam Queries 419
- Tier 1 Placement Questions 16
- Job Queries 39
- Projects 4

29,154 questions

36,976 answers

92,138 comments

34,816 users