Find a shortest path from s to t

Assignment Help Engineering Mathematics

Reference no: EM132141239

Question :

(a) Suppose that you are given an instance of the MST problem on a graph G, with edge weights that are all positive and distinct. Let T be the minimum spanning tree for G returned by Kruskal's algorithm. Now suppose we replace each edge weight w_e by its square w2_e, thereby creating a new instance of the problem with the same graph but different edge weights. Is it true that T is still a minimum spanning tree for this new instance. If you think it is true, give an explanation; otherwise, give a counterexample.

(b) Let G = (V, E) e a directed graph in which every edge has unit length (i.e., length = 1). Design an algorithm that given any two vertices s and t of G, find a shortest path from s to t using O(|E|) time.

Reference no: EM132141239

Questions Cloud

What speedup is possible with pipelining : What is the maximum execution rate without pipelining? What speedup is possible with pipelining?

Would there be any advantages to using the cts and rts frame : Suppose the IEEE 802.11 RTS and CTS frames were as long as the standard DATA and ACK frames.

How does the behavior of dbscan and k-means differ on : Suppose you are given two sets of 100 points that fall within the unit square. One set of points (a) is arranged so that the points are uniformly spaced.

Describe a linear time algorithm for this does di-graph g : Determine whether a given vertex can reach every other vertex in the graph (this is the 1-to-many reachability problem).

Find a shortest path from s to t : Design an algorithm that given any two vertices s and t of G, find a shortest path from s to t using O(|E|) time.

Write an algorithm to determine the two closest cities : Suppose you are given a set of cities (p number of cities) and there longitude and latitude coordinates. You need to determine the two closest cities.

Determine the expected number of die rolls until a coin flip : Explain how to use die rolls to generate unbiased coin flips, and determine the expected number of die rolls until a coin flip is generated.

Write an algorithm to transfer all elements : Write an algorithm to transfer all elements from S to T so that the top of S is the first to be inserted onto T, and the bottom of S ends up at the top of T.

What was the human reason for encoding this information : What kind of encoding would this be and what was the human reason for encoding this information?

User Account

All Pages