I think 11.

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