retagged by
564 views
1 votes
1 votes

retagged by

1 Answer

Best answer
6 votes
6 votes

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

selected by

Related questions

1 votes
1 votes
3 answers
1
Rakesh K asked Nov 27, 2016
3,100 views
5 votes
5 votes
2 answers
2
jenny101 asked Oct 26, 2016
1,172 views
1 votes
1 votes
3 answers
3
3 votes
3 votes
2 answers
4
dd asked Dec 6, 2016
2,604 views
Let P be a shortest path from some vertex s to some other vertex t in a directed graph. If the weight of each edge in the graph is increased by one, P will still be a sho...