Log In
2 votes

in Algorithms 256 views
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

1 Answer

6 votes
Best answer

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 vote
0 answers
TRUE / FALSE Explain Please.. An undirected graph is said to be Hamiltonian if it has a cycle containing all the vertices. Any DFS tree on a Hamiltonian graph must have depth V − 1.
asked Jul 31, 2018 in Algorithms Rishav Kumar Singh 220 views
1 vote
1 answer
Read the following statements below For all the below questions consider the graph as simple and has positive weight edges. (i) Let the cost of the shortest path between two nodes is S.If the weight of every edge in the graph is doubled then weight of the shortest ... iii) We can use Kruskal's algorithm to find Minimum spanning tree of a directed graph . How many of the above statements are true.
asked Dec 13, 2017 in Algorithms VIKAS TIWARI 345 views
1 vote
3 answers
For a given undirected weighted graph G with V number of vertices, if you want to find all pair shortest paths then which one of the following is true ? a) run dijkstra's shortest path algorithm only once. b) run dijkstra's shortest path algorithm V times. What if the given graph is directed ?
asked Jun 26, 2017 in Algorithms Abhisek Saha 397 views
3 votes
2 answers
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 shortest path from s to t. T/F
asked Dec 6, 2016 in Algorithms dd 723 views