Consider the following statement, decide whether it is true or false. If it is t
ID: 3807107 • Letter: C
Question
Consider the following statement, decide whether it is true or false. If it is true, give a short explanation. If it is false, give a counterexample. Suppose we are given an instance of the Shortest s - t Path Problem on a directed graph G. We assume that all edge costs are positive and distinct. Let P be a minimum-cost s - t path for this instance. Now suppose we replace each edge cost c_e by its square, c_e^2, thereby creating a new instance of the problem with the same graph but different costs. True or false? P must still be a minimum-cost s - t path for this new instance.Explanation / Answer
True, if we square the weights of edges in a grpah does not effect the shortest pathe between two nodes. Generally we can say, there will be no change in Minimum spanning tree.
We prove this by counter example, assume the shortest path changes as we square the edge weights.
Now, there is atleast an edge in Old Shortest path S1 is replaced by new shortest path S2. So, new edge should be of less weight than previous one. This means there exist a edge weight W1 < W2 and W12 > W22 which is not possible.