Let T be a tree constructed by Dijkstra%u2019s algorithm in the process of solvi
ID: 3539441 • Letter: L
Question
Let T be a tree constructed by Dijkstra%u2019s algorithm in the process of solving
the single-source shortest-paths problem for a weighted connected graph G.
a. True or false: T is a spanning tree of G?
b. True or false: T is a minimum spanning tree of G?
Need a brief explanation for each.
Design a dynamic programming algorithm for the version of the knapsack
problem in which there are unlimited quantities of copies for each of the n
item kinds given. Indicate the time efficiency of the algorithm.
Explanation / Answer
Q1)
a) True. A spanning tree T of a graph G is a tree which includes all the vertices of G. Dijkstra's algorithm gives a single-source shortest-paths . Considering all the shortest paths, will give a spanning tree since it will contain all the vertices.
b) False. A minimum spanning tree is a spanning tree having least sum of weights. The spanning tree T formed from Dijkstra's algorithm does not tale sum of all paths into account. It only checks for shortest path from a particular source vertex. So, it can not give a minimum spanning tree for the overall graph G.
Ex. - consider a undirected graph G having three vertices A, B and C.
Edge between (A,B) = 3 , (B,C) = 2 and (A,C) = 3
Now, Dijkstra's algorithm with source vertex as A will give shortest path (A,B) = 3 and (A,C) = 3
So, the spanning tree will have sum of weight = 3+3 =^
But, Consider the tree with edges (A,B) and (B,C). It is also a spanning tree .
Also, the sum of the weights for the above tree = 3+2 = 5 which is less than 6.
Therefore, this is the spanning tree.
Q2)
For each w <= W, define m[w] to be the maximum value that can be attained with total weight less than or equal to w.
m[W] then is the solution to the problem.
Observe that m[w] has the following properties:
m[0] = 0(the sum of zero items, i.e., the summation of the empty set)
m[w] = max(v_i + m[w-w_i]) (where w_i <= w and v_i is the value of the i-th kind of item.)
Here the maximum of the empty set is taken to be zero. Calculating the results from up through gives the solution.
Since the calculation of each m[w] involves examining n items, and there are W values of m[w] to calculate, the running time of the dynamic programming solution is O(nW).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.