Shortest path length

Question

Comments

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

Answer 1

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