Question

Answer each of the following in at most two sentences.

1. In a weighted graph G where all edges have weight 1, how can we use Djikstra's algorithm to find a minimum spanning tree?
2. Suppose a dynamic programming algorithm creates an n*m table and to compute each entry of the table it takes a minimum over at most m (previously computed) other entries. What would the running time of this algorithm be, assuming there is no other computations.

Answer 1

Question A)
Dijsktras algorithm traverses graph to find shortest path from starting node to all other nodes, The edges used during this traversal form a tree. If we run dijkstras algorithm and take all used edges it will give as MST. It will be spanning tree because dijsktras algorithm visits all nodes to find distance and it will be minimum beacuse all edges have same weight, hence all spanning trees have same weight.
Question B)
Creating n*m table needs n*m operation. Filling each entry takes m operations and there are n*m entries to be filled so in total it takes n*m*m operations. So final number of operations is n*m+n*m*m which is O(n*m*m) time complexity.


Comment down for any queries
Please give a thumbs up