35 views
True/False

1) Multiplying all edge weight by a positive number might change the graph MST.

2) If all edge in a graph have distinct weight than the shortest path between two vertices is unique.

Thanks

If all edge in a graph have distinct weight than the shortest path between two vertices is unique.

FALSE. Even if no two edges have the same weight, there could be two paths with the same weight. For example, there could be two paths from s to t with lengths 3 + 5 = 8 and 2 + 6 = 8. These paths have the same length (8) even though the edges (2, 3, 5, 6) are all distinct.

Or You can take a triangle graph (complete graph on three vertices) whose edge weights are 2,3,5. Now, you can see that there are two vertices such that there are two different shortest paths between those two vertices, One path is single edge path of weight 5, and another path is two edge path of length 5.

Multiplying all edge weight by a positive number might change the graph MST.

False.

Kruskal’s algorithm only cares about the order of the edge weights, not their absolute values, and adding some fixed value to each edge OR multiplying each edge with a positive number, will not change the sorted order. So, MST will remain same But cost of MST will be changed.

by
1.7k points