Computer Sciences > GATE 2025 SET-2 > Graph Algorithms
Let G be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant a is added to the weight of every edge. Which ONE of the following statements is TRUE about the minimum spanning trees (MSTs) and shortest paths (SPs) in G before and after the edge weight update?
A
Every MST remains an MST, and every SP remains an SP.
B
MSTs need not remain MSTs, and every SP remains an SP.
C
Every MST remains an MST, and SPs need not remain SPs.
D
MSTs need not remain MSTs, and SPs need not remain SPs.

Explanation

Correct : c

Similar Questions

What is the worst-case time complexity of insertion in an AVL tree?
Question #23 Medium
Which operations on a binary search tree have O(h) complexity?
Question #31 Easy
Compare search complexities of sorted array vs balanced BST.
Question #47 Hard

Related Topics

Data Structures Binary Search Tree Time Complexity Algorithm Analysis Tree Algorithms Computer Science