Q27

MCQ2 marks, −0.67

Let $\text{G}$ be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant $\alpha$ 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 $\text{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.

Loading…